Cod sursă (job #120406)

#include <cstdio>

#define N 20
#define I 15

struct pozSt {char linI, colI, dir;} stiva[I +1];
struct poz {char lin, col;} vims[I +1];

char a[N +2][N +2], flag = 0;
int n, m, imm;
char dl[] = {0, 0, 1, 0, -1}, dc[] = {0, 1, 0, -1, 0};

inline void bordare () {
    for (int i = 0; i <= n +1; ++i) {
        a[i][0] = a[i][m +1] = -1;
    }
    for (int j = 0; j <= m +1; ++j) {
        a[0][j] = a[n +1][j] = -1;
    }
}

inline int vecin (int x, int y) {
    for (int i = 1; i <= 4; ++i) {
        if (a[x + dl[i]][y + dc[i]] == 1) {
            return i;
        }
    }

    return 0;
}

inline void afisare () {
    for (int i = 1; i < imm; ++i) {
        printf ("%d %d %d %d\n", stiva[i].linI, stiva[i].colI, stiva[i].linI + (dl[stiva[i].dir]<<1), stiva[i].colI + (dc[stiva[i].dir]<<1));
    }
}

void backtrack (int k) {
    if (flag == 1) {
        return;
    }

    if (k == imm -1) {
        afisare ();
        flag = 1;
    }
    else {
        int i, j;
        for (int p = 1; p <= imm; ++p) {
            if (vims[p].lin != 0) {
                i = vims[p].lin;
                j = vims[p].col;
                int v;
                v = vecin (i, j);
                if (a[i][j] == 1 && v && a[i + (dl[v]<<1)][j + (dc[v]<<1)] == 0) {
                    k++;
                    stiva[k].linI = i;
                    stiva[k].colI = j;
                    stiva[k].dir = v;

                    a[i + dl[v]][j + dc[v]] = 0;
                    a[i + (dl[v]<<1)][j + (dc[v]<<1)] = 1;
                    a[i][j] = 0;

                    vims[p].lin = i + (dl[v]<<1);
                    vims[p].col = j + (dc[v]<<1);


                    backtrack (k);

                    a[i + dl[v]][j + dc[v]] = 1;
                    a[i + (dl[v]<<1)][j + (dc[v]<<1)] = 0;
                    a[i][j] = 1;
                    vims[p].lin = i;
                    vims[p].col = j;
                    k--;
                }
            }
        }
    }
}

int main () {
    freopen ("immortal.in", "r", stdin);
    freopen ("immortal.out", "w", stdout);
    scanf ("%d%d%d", &n, &m, &imm);
    for (int i = 1; i <= imm; ++i) {
        scanf ("%d%d", &vims[i].lin, &vims[i].col);
        a[vims[i].lin][vims[i].col] = 1;
    }

    bordare ();
    backtrack (0);

    return 0;
}