Cod sursa(job #136558)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 15 februarie 2008 17:42:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
//Borland $#!@

#include <stdio.h>

#define MAXN 105

int N, M;
char m[MAXN][MAXN];

int d1[MAXN][MAXN], d2[MAXN][MAXN];

char qx[MAXN * MAXN], qy[MAXN * MAXN];
int q0;

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

int Rx, Ry, Jx, Jy;

void bfs( int Sx, int Sy, int d[MAXN][MAXN] )
{
	d[Sx][Sy] = 1;
	q0 = 0; qx[0] = Sx; qy[0] = Sy;

	for (int i = 0; i <= q0; i++)
	{
		int x = qx[i], y = qy[i];

		for (int k = 0; k < 8; k++)
		{
			int _x = x + dx[k], _y = y + dy[k];
			if (_x < 0 || _x >= N) continue;
			if (_y < 0 || _y >= M) continue;

			if (d[_x][_y] != 0 || m[_x][_y] == 'X') continue;

			d[_x][_y] = d[x][y] + 1;

			q0++; qx[q0] = _x; qy[q0] = _y;
		}
	}
}


int main()
{
	//evident ca nu pot face 2 for (int i;...) fara sa faca scandal idiotu
	int i, j;

	freopen("rj.in", "rt", stdin);
	freopen("rj.out", "wt", stdout);


	scanf("%d %d ", &N, &M);
	for (i = 0; i < N; i++)
	{
		fgets( m[i], MAXN, stdin );
		for (j = 0; j < M; j++)
		{
			if (m[i][j] == 'R')
				Rx = i, Ry = j;
			if (m[i][j] == 'J')
				Jx = i, Jy = j;
		}
	}

	printf("%d %d - %d %d\n", Rx, Ry, Jx, Jy);
	bfs( Rx, Ry, d1 );
	bfs( Jx, Jy, d2 );

	long Min = 0x3f3f3f3f; int MinX = -1, MinY = -1;
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			if (d1[i][j] != 0 && d1[i][j] == d2[i][j])
			{
				if (d1[i][j] < Min)
					Min = d1[i][j],
					MinX = i,
					MinY = j;
			}
	printf("%ld %d %d\n", Min, MinX + 1, MinY + 1);
	return 0;
}