Cod sursă (job #334064)

#include <cstdio>
#include <cstdlib>

using namespace std;

const int NMAX = 25, IMAX = 20;

struct nemuritor{
    int ox, oy;
} nem[IMAX];

struct mystack{
    int ox, oy, dir;
}rasp[IMAX];

int camp[NMAX][NMAX];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m, k;

void afis(){
    freopen("immortal.out", "w", stdout);
    for(int i = k; i > 1; i--)
        printf("%d %d %d %d\n", rasp[i].ox - 1, rasp[i].oy - 1, rasp[i].ox + 2 * dx[rasp[i].dir] - 1, rasp[i].oy + 2 * dy[rasp[i].dir] - 1);
    exit(0);
}

void lupta(int k){
    if(k == 1)
        afis();
    for(int i = 0; i < k; i++){
        int lin = nem[i].ox, col = nem[i].oy;
        for(int d = 0; d < 4; d++){
            int nextx = nem[i].ox + dx[d], nexty = nem[i].oy + dy[d];
            int nextnx = nextx + dx[d], nextny = nexty + dy[d];

            if(camp[nextx][nexty] > -1 && camp[nextnx][nextny] == -1){
                rasp[k] = {lin, col, d};
                camp[lin][col] = -1;
                nem[i] = {nextnx, nextny};
                camp[nextnx][nextny] = i;

                int mort = camp[nextx][nexty];
                if(mort < k - 1){
                    nem[mort] = nem[k - 1];
                    camp[nem[mort].ox][nem[mort].oy] = mort;
                }
                camp[nextx][nexty] = -1;

                lupta(k - 1);

                if(mort < k - 1){
                    nem[k - 1] = nem[mort];
                    camp[nem[k - 1].ox][nem[k - 1].oy] = k - 1;
                    nem[mort] = {nextx, nexty};
                }

                camp[nextx][nexty] = mort;
                camp[nextnx][nextny] = -1;
                nem[i] = {lin, col};
                camp[lin][col] = i;
            }
        }
    }
}

int main()
{
    freopen("immortal.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 2; i <= m + 1; i++)
        camp[0][i] = camp[1][i] = camp[n + 2][i] = camp[n + 3][i] = k + 1;
    for(int i = 2; i <= n + 1; i++)
        camp[i][0] = camp[i][1] = camp[i][m + 2] = camp[i][m + 3] = k + 1;
    for(int i = 2; i <= n + 1; i++)
        for(int j = 2; j <= m + 1; j++)
            camp[i][j] = -1;
    int x, y;
    for(int i = 1; i <= k; i++){
        scanf("%d%d", &x, &y);
        camp[x + 1][y + 1] = 1;
    }
    k = 0;
    for(int i = 2; i <= n + 1; i++){
        for(int j = 2; j <= m + 1; j++)
            if(camp[i][j] == 1){
                nem[k].ox = i;
                nem[k].oy = j;
                camp[i][j] = k;
                k++;
            }
    }
    lupta(k);
    return 0;
}