Cod sursă (job #115124)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NMAX 20
#define IMAX 15
 
char board[NMAX + 1][NMAX + 1]; // 0 daca nu exista, pozitia in ref daca exista
int refx[IMAX + 1], refy[IMAX + 1]; // Linia si coloana la care se afla pionul
int seqx1[IMAX + 1], seqy1[IMAX + 1], seqx2[IMAX + 1], seqy2[IMAX + 1];
int N, M, I, sp;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1}; // NSWE
int done = 0;
FILE *fin, *fout;
 
void bkt()
{
    if (!done) {
        /*printf("%d\n", sp);
        int i, j;
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= M; j++) {
                printf(board[i][j] ? "*" : "-", board[i][j]);
            }
            printf("\n");
        }*/
     
        if (I == 1) {
            int i;
            for (i = 1; i <= sp; i++) {
                fprintf(fout, "%d %d %d %d\n", seqx1[i], seqy1[i], seqx2[i], seqy2[i]);
            }
            done = 1;
        } else {
            int i, j, dir;
            for (i = 1; i <= I; i++) {
                // Randomizare
                int vdir[4];
                for (j = 0; j < 4; j++) {
                    vdir[j] = j;
                }
                if (sp <= 3) {
                    for (j = 0; j < 3; j++) {
                        int pos = j + 1 + rand() % (3 - j);
                        int aux = vdir[j];
                        vdir[j] = vdir[pos];
                        vdir[pos] = aux;
                    }
                }
                for (j = 0; j < 4; j++) { // NSWE
                    dir = vdir[j];
					int x2 = refx[i] + 2 * dx[dir], y2 = refy[i] + 2 * dy[dir];
					int x1 = refx[i] + dx[dir], y1 = refy[i] + dy[dir];
					int x = refx[i], y = refy[i];
                    if (0 < x2 && x2 <= N && 0 < y2 && y2 <= M && board[x1][y1] && board[x2][y2] == 0) {
                        board[x][y] = 0;
                        board[x2][y2] = i;
                        refx[i] += 2 * dx[dir];
                        refy[i] += 2 * dy[dir];
                        int p = board[x1][y1];
     
                        int aux = refx[p];
                        refx[p] = refx[I];
                        refx[I] = aux;
                         
                        aux = refy[p];
                        refy[p] = refy[I];
                        refy[I] = aux;
 
                        board[refx[p]][refy[p]] = p;
                        board[refx[I]][refy[I]] = 0;
     
                        I--;
                        sp++;
                        seqx1[sp] = x;
                        seqy1[sp] = y;
                        seqx2[sp] = x2;
                        seqy2[sp] = y2;
     
                        bkt();
 
                        I++;
                        sp--;
                         
                        aux = refx[p];
                        refx[p] = refx[I];
                        refx[I] = aux;               
                         
                        aux = refy[p];
                        refy[p] = refy[I];
                        refy[I] = aux;
     
                        board[refx[p]][refy[p]] = p;
                        board[refx[I]][refy[I]] = I;
     
                        board[refx[i]][refy[i]] = 0;
                        board[refx[i] - 2 * dx[dir]][refy[i] - 2 * dy[dir]] = i;
                        refx[i] -= 2 * dx[dir];
                        refy[i] -= 2 * dy[dir];
                    }
                }
            }
        }
    }
}
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 x, y;
        fscanf(fin, "%d%d", &x, &y);
        board[x][y] = i;
        refx[i] = x;
        refy[i] = y;
    }
 
    bkt();
 
    fclose(fin);
    fclose(fout);
    return 0;
}