Cod sursă (job #116139)

#include <cstdio>
#include <cstdlib>
#include <ctime>

#define NM_MAX 20
#define I_MAX 15

int rl[I_MAX + 1], rc[I_MAX + 1], lin1[I_MAX + 1], col1[I_MAX + 1], lin2[I_MAX + 1], col2[I_MAX + 1], N, M, I, depth, dl[] = {-1, 1, 0, 0}, dc[] = {0, 0, 1, -1}, flag = 0;

char mat[NM_MAX + 1][NM_MAX + 1];
FILE *fin, *fout;
 
void back()
{
    if (!flag) {
        if (I < 2) {
            int i;
            for (i = 1; i <= depth; i++) {
                fprintf(fout, "%d %d %d %d\n", lin1[i], col1[i], lin2[i], col2[i]);
            }
            flag = 1;
        } else {
            int i, j, d;
            for (i = 1; i <= I; i++) {
                int rnd[4];
                for (j = 0; j < 4; j++) {
                    rnd[j] = j;
                }
                if (depth <= 3) {
                    for (j = 0; j < 3; j++) {
                        int pos = j + 1 + rand()%(3-j);
                        int aux = rnd[j];
                        rnd[j] = rnd[pos];
                        rnd[pos] = aux;
                    }
                }
                for (j = 0; j < 4; j++) {
                    d = rnd[j];
					int l2 = rl[i] + 2 * dl[d], c2 = rc[i] + 2 * dc[d];
					int l1 = rl[i] + dl[d], c1 = rc[i] + dc[d];
					int l = rl[i], c = rc[i];
                    if (0 < l2 && l2 <= N && 0 < c2 && c2 <= M && mat[l1][c1] && mat[l2][c2] == 0) {
                        mat[l][c] = 0;
                        mat[l2][c2] = i;
                        rl[i] = l2;
                        rc[i] = c2;
                        int w = mat[l1][c1];
                        int aux = rl[w];
                        rl[w] = rl[I];
                        rl[I] = aux;
                        aux = rc[w];
                        rc[w] = rc[I];
                        rc[I] = aux;
                        mat[rl[w]][rc[w]] = w;
                        mat[rl[I]][rc[I]] = 0;
                        I--;
                        depth++;
                        lin1[depth] = l;
                        col1[depth] = c;
                        lin2[depth] = l2;
                        col2[depth] = c2;
                        back();
                        I++;
                        depth--;                        
                        aux = rl[w];
                        rl[w] = rl[I];
                        rl[I] = aux;                                       
                        aux = rc[w];
                        rc[w] = rc[I];
                        rc[I] = aux;  
                        mat[rl[w]][rc[w]] = w;
                        mat[rl[I]][rc[I]] = I;    
                        mat[rl[i]][rc[i]] = 0;
                        mat[l][c] = i;
                        rl[i] = l;
                        rc[i] = c;
                    }
                }
            }
        }
    }
}

int main()
{
	srand(time(NULL));
    fin = fopen("immortal.in", "r");
    fout = fopen("immortal.out", "w");
 
    fscanf(fin, "%d%d%d", &N, &M, &I);
 
    int i;
    for (i = 1; i <= I; i++) {
        int l, c;
        fscanf(fin, "%d%d", &l, &c);
        rl[i] = l;
        rc[i] = c;
		mat[l][c] = i;
    }
 
    back();
 
    fclose(fin);
    fclose(fout);
    return 0;
}