Cod sursă (job #255697)

#include <cstdio>
using namespace std;

int NR, ok, n, m, k, f[22][22], t[22], fr[22], l[22], c[22];
struct steps{
    int l1, c1, l2, c2;
}st[5002];
inline void back(int R){
    if(R == 1){
        ok = 1;
        for(int i = 1; i <= NR ; ++i)
            printf("%d %d %d %d\n", st[i].l1, st[i].c1, st[i].l2, st[i].c2);
        return ;
    }
    for(int i = 1; i <= k ; ++i){
        if(fr[i]) continue ;
        int l1 = l[i] + 1, c1 = c[i];
        if(f[l1][c1] && l1 <= n){
            int aux = f[l1][c1];
            int la = l[i], ca = c[i];
            st[++NR].l1 = l[i]; st[NR].c1 = c[i];
            st[NR].l2 = l1 + 1; st[NR].c2 = c1;
            f[l1][c1] = 0; fr[aux] = 1;
            f[l[i]][c[i]] = 0;
            l[i] = l1 + 1; c[i] = c1;
            f[l[i]][c[i]] = i;
            back(R - 1); --NR;
            f[l[i]][c[i]] = 0;
            l[i] = la; c[i] = ca;
            f[l1][c1] = aux; fr[aux] = 0;
            f[l[i]][c[i]] = i;
        }if(ok) return ;
        l1 = l[i] - 1, c1 = c[i];
        if(f[l1][c1] && l1 >= 1){
            int aux = f[l1][c1];
            int la = l[i], ca = c[i];
            st[++NR].l1 = l[i]; st[NR].c1 = c[i];
            st[NR].l2 = l1 - 1; st[NR].c2 = c1;
            f[l1][c1] = 0; fr[aux] = 1;
            f[l[i]][c[i]] = 0;
            l[i] = l1 - 1; c[i] = c1;
            f[l[i]][c[i]] = i;
            back(R - 1); --NR;
            f[l[i]][c[i]] = 0;
            l[i] = la; c[i] = ca;
            f[l1][c1] = aux; fr[aux] = 0;
            f[l[i]][c[i]] = i;
        }if(ok) return ;
        l1 = l[i], c1 = c[i] + 1;
        if(f[l1][c1] && c1 <= m){
            int aux = f[l1][c1];
            int la = l[i], ca = c[i];
            st[++NR].l1 = l[i]; st[NR].c1 = c[i];
            st[NR].l2 = l1; st[NR].c2 = c1 + 1;
            f[l1][c1] = 0; fr[aux] = 1;
            f[l[i]][c[i]] = 0;
            l[i] = l1; c[i] = c1 + 1;
            f[l[i]][c[i]] = i;
            back(R - 1); --NR;
            f[l[i]][c[i]] = 0;
            l[i] = la; c[i] = ca;
            f[l1][c1] = aux; fr[aux] = 0;
            f[l[i]][c[i]] = i;
        }if(ok) return ;
        l1 = l[i], c1 = c[i] - 1;
        if(f[l1][c1] && c1 >= 1){
            int aux = f[l1][c1];
            int la = l[i], ca = c[i];
            st[++NR].l1 = l[i]; st[NR].c1 = c[i];
            st[NR].l2 = l1; st[NR].c2 = c1 - 1;
            f[l1][c1] = 0; fr[aux] = 1;
            f[l[i]][c[i]] = 0;
            l[i] = l1; c[i] = c1 - 1;
            f[l[i]][c[i]] = i;
            back(R - 1); --NR;
            f[l[i]][c[i]] = 0;
            l[i] = la; c[i] = ca;
            f[l1][c1] = aux; fr[aux] = 0;
            f[l[i]][c[i]] = i;
        }if(ok) return ;
    }
}
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", &l[i], &c[i]);
        f[l[i]][c[i]] = i;
    }
    back(k);
    return 0;
}