Cod sursa(job #124155)

Utilizator blahblahblahblah blahblah Data 18 ianuarie 2008 13:10:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#include <string.h>

#define NMAX 110

int N, M;

char a[NMAX][NMAX]; 
int R[NMAX][NMAX], J[NMAX][NMAX];
char s[NMAX];
char viz[NMAX][NMAX];

int XX[NMAX * NMAX];
int YY[NMAX * NMAX];

int dx[] = { 0, 0, 1, 1, 1,-1,-1,-1};
int dy[] = {-1, 1,-1, 0, 1,-1, 0, 1};

void baga_df(int x, int y, int dst[NMAX][NMAX])
{
	memset(viz, 0, sizeof(viz));
	
	int p = 0, q = 0, xx, yy, i, j;
	XX[p] = x; YY[p] = y;
	
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++) dst[i][j] = 1000000;
	
	viz[x][y] = 1;
	dst[x][y] = 1;
	
	while (p <= q) {
		x = XX[p]; y = YY[p];
		p++;
		
		for (i = 0; i < 8; i++) {
			xx = x + dx[i]; yy = y + dy[i];
			
			if (1 <= xx && xx <= N && 1 <= yy && yy <= M && !viz[xx][yy] && a[xx][yy] != 'X') {
				q++; XX[q] = xx; YY[q] = yy;
				viz[xx][yy] = 1;
				dst[xx][yy] = dst[x][y] + 1;
			}
		}
	}
}


int main()
{
	int i, j, rx, ry, jx, jy;
	char c;
	
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	
	scanf("%d %d\n", &N, &M);
	
	for (i = 1; i <= N; i++) {
		fgets(s, 110, stdin);
		
		for (j = 1; j <= M; j++) {
			c = s[j - 1];
			a[i][j] = c;
			if (c == 'R') rx = i, ry = j;
			if (c == 'J') jx = i, jy = j;
		}
	}
	
	baga_df(rx, ry, R);
	baga_df(jx, jy, J);
	
	int mn = 1000000, sx = 0, sy = 0;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++)
			if (R[i][j] == J[i][j] && R[i][j] < mn) mn = R[i][j], sx = i, sy = j;
			
	printf("%d %d %d\n", mn, sx, sy);
	
return 0;
}