Cod sursa(job #825832)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 29 noiembrie 2012 18:12:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <queue>
#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("rj.in");
ofstream out ("rj.out");

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

int A[200][200];
int B[200][200];
char S[110];

int main ()
{	
	int N, M;
	int i, j;
	int Rx, Ry;
	int Jx, Jy;
	int nowx, nowy;
	int vx, vy;
	char c;
	
	queue < pair < int, int > > Q;
	pair < int, int > now;
	
	//scanf ("%d %d\n", &N, &M);
	in >> N >> M;
	//in.ignore ();
	
	for (i = 0; i <= M + 1; i ++){
		A[0][i] = -1;
		A[N + 1][i] = -1;
		B[0][i] = -1;
		B[N + 1][i] = -1;
	}
	
	for (i = 0; i <= N + 1; i ++){
		A[i][0] = -1;
		A[i][M + 1] = -1;
		B[i][0] = -1;
		B[i][M + 1] = -1;
	}
	
	/*for (i = 0; i <= N + 1; i ++){
		for (j = 0; j <= M + 1; j ++)
			cout << A[i][j] << " ";
		
		cout << "\n";
	}*/
	
	for (i = 1; i <= N; i ++){
		in.get ();
		in.get (S, 105);
		//in.getline (S, 105);
		
		for (j = 0; j < M; j ++){
			c = S[j];
			
			if (c == 'R'){
				A[i][j + 1] = 1;
				B[i][j + 1] = -1;
				Rx = i;
				Ry = j + 1;
			}
			
			if (c == 'J'){
				B[i][j + 1] = 1;
				A[i][j + 1] = -1;
				Jx = i;
				Jy = j + 1;
			}
			
			if (c == 'X'){
				A[i][j + 1] = -1;
				B[i][j + 1] = -1;
			}
		}
	}
	
	/*for (i = 0; i <= N + 1; i ++){
		for (j = 0; j <= M + 1; j ++)
			cout << A[i][j] << " ";
		
		cout << "\n";
	}*/
	
	//cout << "\n" << Rx << " " << Ry << "\n" << Jx << " " << Jy;
		
	Q.push (make_pair (Rx, Ry));
	
	while (!Q.empty ()){
		now = Q.front ();
		Q.pop ();
		nowx = now.first;
		nowy = now.second;
		
		for (i = 0; i < 8; i ++){
			vx = nowx + dx[i];
			vy = nowy + dy[i];
			
			if (A[vx][vy] == -1)
				continue;
			
			if ((!A[vx][vy]) || (A[vx][vy] > A[nowx][nowy] + 1)){
				A[vx][vy] = A[nowx][nowy] + 1;
				Q.push (make_pair (vx, vy));
			}
		}
	}
	
	Q.push (make_pair (Jx, Jy));
	
	while (!Q.empty ()){
		now = Q.front ();
		Q.pop ();
		nowx = now.first;
		nowy = now.second;
		
		for (i = 0; i < 8; i ++){
			vx = nowx + dx[i];
			vy = nowy + dy[i];
			
			if (B[vx][vy] == -1)
				continue;
			
			if ((!B[vx][vy]) || (B[vx][vy] > B[nowx][nowy] + 1)){
				B[vx][vy] = B[nowx][nowy] + 1;
				Q.push (make_pair (vx, vy));
			}
			
			if (A[vx][vy] == B[vx][vy]){
				out << A[vx][vy] << " " << vx << " " << vy;
				
				return 0;
			}
		}
	}
		
	return 0;
}