Cod sursă (job #114303)

#include <fstream>
#include <algorithm>
#define DIM 25
#define infile "immortal.in"
#define outfile "immortal.out"
 
using namespace std;
 
ifstream f(infile);
ofstream g(outfile);
 
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int n, m, nr, fnd;
 
int A[DIM][DIM], posX[DIM], posY[DIM], go[DIM], solX[DIM], solY[DIM];
 
bool ok[DIM];
 
void writeSol() {
    for (int i = 1; i < nr; ++i) {
        g << solX[i] << ' ' << solY[i] << ' ';
        solX[i] -= 2 * dx[go[i]];
        solY[i] -= 2 * dy[go[i]];
        g << solX[i] << ' ' << solY[i] << '\n';
    }
}
 
void back(int k) {
    if (fnd)
        return;
    if (k == nr) {
        writeSol();
        fnd = 1;
        return;
    }
 
    for (int i = 1; i <= nr; ++i) {
        if (ok[i])
            continue;
 
        int xc = posX[i];
        int yc = posY[i];
        for (int d = 0; d < 4; ++d) {
            int xv = xc + dx[d];
            int yv = yc + dy[d];
            int xvv = xc - dx[d];
            int yvv = yc - dy[d];
            int valv = A[xv][yv];
 
            if (valv <= 0 || A[xvv][yvv] != 0)
                continue;
 
            go[k] = d;
            ok[i] = 1;
            solX[k] = xv;
            solY[k] = yv;
            posX[valv] -= 2 * dx[d];
            posY[valv] -= 2 * dy[d];
            A[xc][yc] = A[xv][yv] = 0;
            A[xvv][yvv] = valv;
 
            back(k + 1);
 
            ok[i] = 0;
            posX[valv] += 2 * dx[d];
            posY[valv] += 2 * dy[d];
            A[xc][yc] = i;
            A[xv][yv] = valv;
            A[xvv][yvv] = 0;
        }
    }
}
 
int main() {
    f >> n >> m >> nr;
 
    for (int i = 0; i <= n + 1; ++i)
        A[i][0] = A[i][m + 1] = -1;
    for (int i = 1; i <= m; ++i)
        A[0][i] = A[n + 1][i] = -1;
 
    for (int i = 1; i <= nr; ++i) {
        int x, y;
        f >> x >> y;
        A[x][y] = i;
        posX[i] = x;
        posY[i] = y;
    }
 
    back(1);
 
    return 0;
}