Cod sursa(job #625963)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 25 octombrie 2011 22:25:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

char map[105][105];
int N , M , sir[10] = {-1 , 0 , 1 , 0 , -1 , -1 , 1 , 1 , -1};
queue <pair <char , char> > Q;
bool viz[105][105];
int costR[105][105] , costJ[105][105];


void bfs (int x , int y , int dest1 , int dest2 , int cost[105][105])
{
	int nod1 , nod2;
	
	cost[x][y] = 1;
	
	Q.push (make_pair (x , y));
	
	while (!Q.empty ())
	{
		nod1 = Q.front ().first;
		nod2 = Q.front ().second;
		
		if (nod1 == dest1 && nod2 == dest2)
			break;
		
		for (int i = 1 ; i < 9 ; ++i)
		{
			if (viz[nod1 + sir[i]][nod2 + sir[i + 1]])
				continue;
			
			if (map[nod1 + sir[i]][nod2 + sir[i + 1]] == ' ')
			{
				viz[nod1 + sir[i]][nod2 + sir[i + 1]] = 1;
				cost[nod1 + sir[i]][nod2 + sir[i + 1]] = cost[nod1][nod2] + 1;
				
				Q.push (make_pair (nod1 + sir[i] , nod2 + sir[i + 1]));
			}
		}
		
		Q.pop ();
	}

}
int main ()
{
	ifstream f ("rj.in");
	ofstream g ("rj.out");
	
	int cr1 , cr2 , cj1 , cj2;
	
	f >> N >> M;
	
	f.get ();
	
	for (int i = 1 ; i <= N ; ++i)
	{
		f.getline (map[i] , 105);
		
		for (int j = 0 ; j < M ; ++j)
		{
			
			if (map[i][j] == 'R')
			{
				cr1 = i;
				cr2 = j;
			}
				
			else if (map[i][j] == 'J')
			{
				cj1 = i;
				cj2 = j;
			}
		}
		
	}
	
	bfs (cr1 , cr2 , cj1 , cj2 , costR);
	
	memset (viz , 0 , sizeof (viz));
	
	bfs (cj1 , cj2 , cr1 , cr2 , costJ);
	
	int minim = 99999 , ics , igrec;
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 0 ; j < M ; ++j)
			if (costR[i][j] == costJ[i][j] && costR[i][j] != 0 && costR[i][j] < minim)
			{
				minim = costR[i][j];
				ics = i;
				igrec = j + 1;
			}

	
	g << minim << " " << ics << " " << igrec;

	return 0;
}