Cod sursă (job #333356)

#include <bits/stdc++.h>
using namespace std;

int NR, n, m, k, l[22], c[22];
int Sol[16][4];
bool ok = 0, v[22];
int f[22][22];
int pos[22];
inline void back(int contor){
    ++NR;
    if(contor == k - 1){
        ok = 1;
        for(int i = 0; i < contor ; ++i)
            printf("%d %d %d %d\n", Sol[i][0], Sol[i][1], Sol[i][2], Sol[i][3]);
        exit(0);
    }
    for(int i = 1; i <= k - contor && !ok ; ++i){
        if(f[l[i]][c[i] - 1] > 0 && f[l[i]][c[i] - 2] == 0 && c[i] - 2 >= 1){
            int aux = f[l[i]][c[i] - 1];
            f[l[i]][c[i] - 1] = 0;
            f[l[i]][c[i] - 2] = f[l[i]][c[i]];
            f[l[i]][c[i]] = 0;
            Sol[contor][0] = l[i];
            Sol[contor][1] = c[i];
            Sol[contor][2] = l[i];
            Sol[contor][3] = c[i] - 2;
            c[i] -= 2;
            l[aux] = l[k - contor];
            c[aux] = c[k - contor];
            if(aux < k - contor)
            f[l[aux]][c[aux]] = aux;
            back(contor + 1);
            f[l[aux]][c[aux]] = k - contor;
            c[i] += 2;
            l[aux] = l[i];
            c[aux] = c[i] - 1;
            f[l[i]][c[i] - 1] = aux;
            v[aux] = 0;
            f[l[i]][c[i]] = f[l[i]][c[i] - 2];
            f[l[i]][c[i] - 2] = 0;
        }
        if(f[l[i]][c[i] + 1] > 0 && f[l[i]][c[i] + 2] == 0 && c[i] + 2 <= m){
            int aux = f[l[i]][c[i] + 1];
            f[l[i]][c[i] + 1] = 0;
            f[l[i]][c[i] + 2] = f[l[i]][c[i]];
            f[l[i]][c[i]] = 0;
            Sol[contor][0] = l[i];
            Sol[contor][1] = c[i];
            Sol[contor][2] = l[i];
            Sol[contor][3] = c[i] + 2;
            c[i] += 2;
            l[aux] = l[k - contor];
            c[aux] = c[k - contor];
            if(aux < k - contor)
            f[l[aux]][c[aux]] = aux;
            back(contor + 1);
            f[l[aux]][c[aux]] = k - contor;
            c[i] -= 2;
            l[aux] = l[i];
            c[aux] = c[i] + 1;
            f[l[i]][c[i] + 1] = aux;
            v[aux] = 0;
            f[l[i]][c[i]] = f[l[i]][c[i] + 2];
            f[l[i]][c[i] + 2] = 0;
        }
        if(f[l[i] - 1][c[i]] > 0 && f[l[i] - 2][c[i]] == 0 && l[i] - 2 >= 1){
            int aux = f[l[i] - 1][c[i]];
            f[l[i] - 1][c[i]] = 0;
            f[l[i] - 2][c[i]] = f[l[i]][c[i]];
            f[l[i]][c[i]] = 0;
            Sol[contor][0] = l[i];
            Sol[contor][1] = c[i];
            Sol[contor][2] = l[i] - 2;
            Sol[contor][3] = c[i];
            l[i] -= 2;
            l[aux] = l[k - contor];
            c[aux] = c[k - contor];
            if(aux < k - contor)
            f[l[aux]][c[aux]] = aux;
            back(contor + 1);
            f[l[aux]][c[aux]] = k - contor;
            l[i] += 2;
            l[aux] = l[i] - 1;
            c[aux] = c[i];
            f[l[i] - 1][c[i]] = aux;
            v[aux] = 0;
            f[l[i]][c[i]] = f[l[i] - 2][c[i]];
            f[l[i] - 2][c[i]] = 0;
        }
        if(f[l[i] + 1][c[i]] > 0 && f[l[i] + 2][c[i]] == 0 && l[i] + 2 <= n){
            int aux = f[l[i] + 1][c[i]];
            f[l[i] + 1][c[i]] = 0;
            f[l[i] + 2][c[i]] = f[l[i]][c[i]];
            f[l[i]][c[i]] = 0;
            Sol[contor][0] = l[i];
            Sol[contor][1] = c[i];
            Sol[contor][2] = l[i] + 2;
            Sol[contor][3] = c[i];
            l[i] += 2;
            l[aux] = l[k - contor];
            c[aux] = c[k - contor];
            if(aux < k - contor)
            f[l[aux]][c[aux]] = aux;
            back(contor + 1);
            f[l[aux]][c[aux]] = k - contor;
            l[i] -= 2;
            l[aux] = l[i] + 1;
            c[aux] = c[i];
            f[l[i] + 1][c[i]] = aux;
            v[aux] = 0;
            f[l[i]][c[i]] = f[l[i] + 2][c[i]];
            f[l[i] + 2][c[i]] = 0;
        }
    }
}
struct handi{
    int l, c;
}a[20];
inline bool cmp(handi i, handi j){
    if(i.l != j.l) return i.l < j.l;
    return i.c < j.c;
}
int main()
{
    freopen("immortal.in", "r", stdin);
    freopen("immortal.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k ; ++i)
        scanf("%d%d", &a[i].l, &a[i].c);
    sort(a + 1, a + k + 1, cmp);
    for(int i = 1; i <= k ; ++i){
        l[i] = a[i].l, c[i] = a[i].c;
        f[l[i]][c[i]] = i;
    }
    back(0);
    return 0;
}