Cod sursa(job #403306)

Utilizator Addy.Adrian Draghici Addy. Data 24 februarie 2010 20:28:35
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>
#define INF 1 << 30
#define Nmax 102

char R[Nmax][Nmax], J[Nmax][Nmax], t;
int DR[Nmax][Nmax], DJ[Nmax][Nmax], C[2][Nmax * Nmax], n, m, i, j, x, y, k, X1, Y1, X2, Y2, p, u, xsol, ysol, sol;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
	
	FILE *f = fopen("rj.in", "r");
	FILE *g = fopen("rj.out", "w");
	
	fscanf(f, "%d %d\n", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			fscanf(f, "%c", &t);
			if (t == ' ')
				R[i][j] = J[i][j] = ' ';
			else {
				if (t == 'R')
					X1 = i, Y1 = j;
				if (t == 'J')
					X2 = i, Y2 = j;
				R[i][j] = J[i][j] = 'X';
			}
		}
		fscanf(f, "%c", &t);
	}
	
	for (i = 0; i <= m + 1; i++)
		R[0][i] = J[0][i] = R[n+1][i] = J[n+1][i] = 'X';
	for (i = 0; i <= n + 1; i++)
		R[i][0] = J[i][0] = R[i][m+1] = J[i][m+1] = 'X';
	
	C[0][1] = X1, C[1][1] = Y1, DR[X1][Y1] = 1;
	for (p = u = 1; p <= u; p++) {
		i = C[0][p], j = C[1][p];
		for (k = 0; k < 8; k++) {
			x = i + dx[k];
			y = j + dy[k];
			if (R[x][y] != 'X') {
				R[x][y] = 'X';
				u++, C[0][u] = x, C[1][u] = y;
				DR[x][y] = DR[i][j] + 1;
			}
		}
	}
	
	C[0][1] = X2, C[1][1] = Y2, DJ[X2][Y2] = 1;
	for (p = u = 1; p <= u; p++) {
		i = C[0][p], j = C[1][p];
		for (k = 0; k < 8; k++) {
			x = i + dx[k];
			y = j + dy[k];
			if (J[x][y] != 'X') {
				J[x][y] = 'X';
				u++, C[0][u] = x, C[1][u] = y;
				DJ[x][y] = DJ[i][j] + 1;
			}
		}
	}
	
	for (i = 1, sol = INF; i <= n; i++)
		for (j = 1; j <= m; j++)
			if ((DR[i][j] == DJ[i][j] && DR[i][j] != 0) && DR[i][j] < sol)
				sol = DR[i][j], xsol = i, ysol = j;
	
	fprintf(g, "%d %d %d", sol, xsol, ysol);
	
	fclose(f); fclose(g);
	
	return 0;
}