Cod sursă (job #116147)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NM_MAX 20
#define I_MAX 15
 
FILE *fin, *fout;
int N, M, I;
int mat[NM_MAX + 2][NM_MAX + 2];
int rl[I_MAX + 1], rc[I_MAX + 1];
int sol[(I_MAX - 1) * 4 + 1];
int depth;
bool flag;
int dl[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}, rnd[] = {0, 1, 2, 3};
 
void back()
{
    int i, j, aux, chg;
    if (!flag) { // Daca nu am gasit inca solutie
        if (depth == I - 1) { // Afisam
            for (i = 0; i < depth; ++i) {
                int pi = (i << 2);
                fprintf(fout, "%d %d %d %d\n", sol[pi + 1], sol[pi + 2], sol[pi + 3], sol[pi + 4]);
            }
            flag = true;
        } else {
            int max = I - depth;
            for (i = 1; i <= max; ++i) {
                for (j = 0; j < 4; ++j) { // Pentru fiecare directie
                    int d = rnd[j];
                    int al = rl[i], ac = rc[i];
                    int exl = rl[i] - dl[d], exc = rc[i] - dc[d];
                    int acl = rl[i] + dl[d], acc = rc[i] + dc[d];
                    if (mat[exl][exc] > 0 && mat[acl][acc] == 0) {
                        mat[rl[max]][rc[max]] = mat[al][ac];
                        mat[al][ac] = 0;
                        rl[i] = rl[max];
                        rc[i] = rc[max];
 
                        mat[acl][acc] = mat[exl][exc];
                        mat[exl][exc] = 0;
                        rl[mat[acl][acc]] = acl;
                        rc[mat[acl][acc]] = acc;

						int dp = (depth << 2);
                        sol[++dp] = exl;
                        sol[++dp] = exc;
                        sol[++dp] = acl;
                        sol[++dp] = acc;
                        ++depth;
 
                        back();
 
                        --depth;
                        mat[exl][exc] = mat[acl][acc];
                        mat[acl][acc] = 0;
                        rl[mat[exl][exc]] = exl;
                        rc[mat[exl][exc]] = exc;
 
                        rl[i] = al;
                        rc[i] = ac;
                        mat[al][ac] = i;
                        mat[rl[max]][rc[max]] = max;
                    }
                }
            }
        }
    }
}
 
int main()
{
    fin = fopen("immortal.in", "r");
    fout = fopen("immortal.out", "w");
 
    fscanf(fin, "%d%d%d", &N, &M, &I);
    int i, j;
    for (i = 1; i <= I; ++i) {
        int l, c;
        fscanf(fin, "%d%d", &l, &c);
        mat[l][c] = i;
        rl[i] = l;
        rc[i] = c;
    }
 
    // Bordam matricea
    for (i = 1; i <= N; ++i) {
        mat[i][0] = mat[i][M + 1] = -77;
    }
    for (i = 1; i <= M; i++) {
        mat[0][i] = mat[N + 1][i] = -77;
    }
 
    srand(time(NULL));
    back();
 
    fclose(fin);
    fclose(fout);
    return 0;
}