Cod sursă (job #644795)

#pragma warning(disable: 4996)

#include <stdio.h>

int n, m, k;
int v[22][22];
int imm[15][2];
int mutari[15][4], dim;
int diri[4] = { -1, 0, 1, 0 };
int dirj[4] = { 0, 1, 0, -1 };

void printStage() {
	int i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++)
			printf("%d ", v[i][j]);
		printf("\n");
	}
	printf("\n");
}

int getSolution(int depth) {
	if (depth == 1)
		return;
	int i, dir, l, c, l1, c1, l2, c2, mort, sol_found = 0;
	for (i = 0; i < 15; i++) 
		if (imm[i][0] > 0) {
			l = imm[i][0];
			c = imm[i][1];
			for (dir = 0; dir < 4; dir++) {
				l1 = imm[i][0] + diri[dir];
				c1 = imm[i][1] + dirj[dir];
				l2 = l1 + diri[dir];
				c2 = c1 + dirj[dir];
			
				if (v[l1][c1] > 0 && v[l2][c2] == 0) {
					//printf("%d %d %d %d\n", l, c, l2, c2);

					v[l][c] = 0;
					v[l2][c2] = i;
					imm[i][0] = l2;
					imm[i][1] = c2;
					mort = v[l1][c1];
					v[l1][c1] = 0;
					imm[mort][0] = imm[mort][1] = 0;

					if (getSolution(depth - 1)) {
						mutari[dim][0] = l;
						mutari[dim][1] = c;
						mutari[dim][2] = l2;
						mutari[dim][3] = c2;
						dim++;
						sol_found = 1, dir = 4, i = 15;
					}
					else {
						v[l][c] = i;
						imm[i][0] = l;
						imm[i][1] = c;
						v[l2][c2] = 0;
						v[l1][c1] = mort;
						imm[mort][0] = l1;
						imm[mort][1] = c1;
					}
				}
			}
		}
	return sol_found;
}

int main() {
	FILE* fin, * fout;
	int i, j, x, y, cnt;

	fin = fopen("immortal.in", "r");
	fscanf(fin, "%d%d%d", &n, &m, &k);
	cnt = 0;
	for (i = 0; i < k; i++) {
		fscanf(fin, "%d%d", &x, &y);
		v[x][y] = ++cnt;
		imm[cnt][0] = x;
		imm[cnt][1] = y;
	}
	fclose(fin);

	for (x = 0; x < n + 2; x++)
		v[x][0] = v[x][m + 1] = -1;
	for (y = 0; y < m + 2; y++)
		v[0][y] = v[n + 1][y] = -1;
	getSolution(cnt);

	fout = fopen("immortal.out", "w");
	for (i = dim - 1; i > -1; i--) {
		//printStage(i);
		for (j = 0; j < 4; j++)
			fprintf(fout, "%d ", mutari[i][j]);
		fputc('\n', fout);
	}
	fclose(fout);

	return 0;
}