Cod sursa(job #150677)

Utilizator HolyBladeOld Radu HolyBlade Data 7 martie 2008 11:33:30
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <stdio.h>
#include <string.h>

#define nmax 110

long i, j, k, n, m, viz[nmax][nmax], xx[nmax * nmax], yy[nmax*nmax], R[nmax][nmax], J[nmax][nmax], dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}, rx = 0, ry = 0, jx = 0, jy = 0;
char s[nmax], a[nmax][nmax], c;

void lee(long x, long y, long dist[nmax][nmax]) {
	long ipr, jpr, p = 0, q = 1, x1, y1;

	memset(viz, 0, sizeof(viz));
	xx[1] = x;
	yy[1] = y;
	dist[x][y] = 1;
	viz[x][y] = 1;

	for(ipr = 1;ipr <= n; ++ipr) {
		for(jpr = 1;jpr <= m; ++jpr) {
			dist[ipr][jpr] = 10000;
		}
	}

    p = 0;
    q = 1;
    dist[x][y] = 0;
    
	while (p <= q) {
		++p;
		x = xx[p];
		y = yy[p];

		for (ipr = 0; ipr < 8; ++ipr) {
			x1 = x + dx[ipr];
			y1 = y + dy[ipr];
			if (viz[x1][y1] == 0 && a[x1][y1] != 'X' && 1 <= x1 && n >= x1 && 1 <= y1 && m >= y1) {
				++q;
				xx[q] = x1;
				yy[q] = y1;
				viz[x1][y1] = 1;
				dist[x1][y1] = dist[x][y] + 1;
			}
		}
	}
}

int main() {
    long min = 32000, e, r;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%ld %ld\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;
            }
		}
	}

	lee(rx, ry, R);
    lee(jx, jy, J);
    
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= m; ++j) {
            if (R[i][j] == J[i][j] && R[i][j] < min) {
                min = R[i][j];
                e = i;
                r = j;
            }
		}
	}
    
    printf("%ld %ld %ld",min + 1, e, r);
    return 0;
}