Cod sursa(job #688321)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 23 februarie 2012 14:02:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const short int xd[] = {1, 0, 0, -1, 1, 1, -1, -1};

const short int yd[] = {0, 1, -1, 0, 1, -1, -1, 1};

int main()
{
	
	short int N, M, i, j, sol, harta[105][105], hartaR[105][105], hartaJ[105][105];

	char c;
	
	pair<short int, short int> r_pos, j_pos, now;
	
	freopen("rj.in", "r", stdin);
	
	scanf("%hd %hd", &N, &M);
	
	for(i=1;i<=N;++i)
	{
		scanf("\n");

		for(j=1;j<=M;++j)
		{
			scanf("%c", &c);

			if(c == ' ')
				harta[i][j] = 0;
			else if(c == 'X')
				harta[i][j] = 1;
			else if(c == 'R')
				r_pos = make_pair(i, j);
			else if(c == 'J')
				j_pos = make_pair(i, j);

		}

	}

	fclose(stdin);

	for(i=0;i<=N+1;++i)
		harta[i][0] = harta[i][M+1] = 1;
	
	for(i=0;i<=M+1;++i)
		harta[0][i] = harta[N+1][i] = 1;
	
	hartaR[r_pos.first][r_pos.second] = 1;
	hartaJ[j_pos.first][j_pos.second] = 1;

	queue<pair<short int, short int> > QR;
	queue<pair<short int, short int> > QJ;

	QR.push(r_pos);
	QJ.push(j_pos);

	while(!QR.empty() || !QJ.empty())
	{
		now = QR.front();
		
		for(i=0;i<8;++i)
			if(!harta[now.first+xd[i]][now.second+yd[i]] && !hartaR[now.first+xd[i]][now.second+yd[i]])
			{
				QR.push(make_pair(now.first+xd[i], now.second+yd[i]));
				hartaR[now.first+xd[i]][now.second+yd[i]] = hartaR[now.first][now.second] + 1;
			}

		QR.pop();
		
		now = QJ.front();

		for(i=0;i<8;++i)
			if(!harta[now.first+xd[i]][now.second+yd[i]] && !hartaJ[now.first+xd[i]][now.second+yd[i]])
			{
				QJ.push(make_pair(now.first+xd[i], now.second+yd[i]));
				hartaJ[now.first+xd[i]][now.second+yd[i]] = hartaJ[now.first][now.second] + 1;
			}

		QJ.pop();
	}

	sol = 10005;
	
	short int sX=0, sY=0;

	for(i=0;i<=N;++i)
		for(j=0;j<=M;++j)
			if(hartaR[i][j] == hartaJ[i][j] && hartaR[i][j] && hartaJ[i][j] && sol >= hartaR[i][j])
				if(sol == hartaR[i][j] && sX > i)
					sol = hartaR[i][j], sX = i, sY = j;
				else if(sol > hartaR[i][j])
					sol = hartaR[i][j], sX = i, sY = j;

	freopen("rj.out", "w", stdout);
	
	cout<<sol<<" "<<sX<<" "<<sY<<"\n";

	fclose(stdout);

	return 0;

}