Cod sursa(job #552857)

Utilizator Catah15Catalin Haidau Catah15 Data 12 martie 2011 23:19:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <string>

using namespace std;

#define maxN 105
#define PB push_back
#define PF pop_front


int N, M;
bool a[maxN][maxN];
int ll[] = {-1, -1, 0, 1, 1, 1, 0, -1}, col[] = {0, -1, -1, -1, 0, 1, 1, 1};
int R[maxN][maxN], J[maxN][maxN];
int x1, x2, y11, y2;



void bf (int x1, int y1, int who[maxN][maxN])
{
	deque < int > coada[3];
	
	
	coada[1].PB(x1);
	coada[2].PB(y1);
	
	memset (who, -1, sizeof(who));
	
	
	who[x1][y1] = 1;
	
	for ( ; coada[1].size(); )
	{
		int x = coada[1][0], y = coada[2][0];
		
		for (int i = 0; i < 8; ++ i)
		{
			if (x + ll[i] < 1 || x + ll[i] > N)
				continue;
			if (y + col[i] < 1 || y + col[i] > M)
				continue;
			
			int xp = x + ll[i], yp = y + col[i];
			
			if (a[xp][yp])
				continue;
			
			if (who[xp][yp] != - 1)
				continue;
			
			coada[1].PB(xp);
			coada[2].PB(yp);
			
			who[xp][yp] = who[x][y] + 1;
		}
		
		coada[1].PF();
		coada[2].PF();
	}
	
}



int main()
{
	ifstream f("rj.in");
	ofstream g("rj.out");
	
	
	f >> N >> M;
	
	memset (R, -1, sizeof(R));
	memset (J, -1, sizeof(J));
	
	
	for (int i = 1; i <= N; ++ i)
	{	
		f.get();
		
		for (int j = 1; j <= M; ++ j)
		{
			char c;
			
			f.get(c);
			
			if (c == 'X')
				a[i][j] = true;
			
			if (c == 'R')
			{
				R[i][j] = 1;
				x1 = i;
				y11 = j;
			}
			
			if (c == 'J')
			{
				J[i][j] = 1;
				x2 = i;
				y2 = j;
			}
		}
	}
	
	
	bf (x1, y11, R);
	bf (x2, y2, J);
	
	
	int minim = maxN * maxN, pozi = 0, pozj = 0;
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= M; ++ j)
			if (R[i][j] == J[i][j] && minim > R[i][j] && R[i][j] > 0)
			{
				minim = R[i][j];
				pozi = i;
				pozj = j;
			}

	
	g << minim << " ";
	g << pozi << " " << pozj;
	
	
	f.close();
	g.close();

	return 0;
}