Cod sursa(job #467552)

Utilizator andunhillMacarescu Sebastian andunhill Data 29 iunie 2010 13:02:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<fstream>
#include<queue>
#include<sstream>
#include<algorithm>
using namespace std;
#define P pair<int,int>
ifstream f("rj.in");
ofstream g("rj.out");
P x;
struct map
{	int r,j;
}a[101][101];
struct poz
{	int i,j,tmin;
}min1;
queue<P>ro;
queue<P>jul;
const int dx[8]={-1,0,1,0,1,-1,1,-1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
int N,M;
void citire()
{	char x;
	f>>N>>M;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{	f>>noskipws>>x;
			if(x=='\n'&&j==1)
				f>>noskipws>>x;
			if(x=='R')
			{	ro.push(make_pair(i,j)); a[i][j].r=1 , a[i][j].j=-1; }
			else
				if(x=='J')
				{	jul.push(make_pair(i,j)); a[i][j].j=1 , a[i][j].r=-1; }
				else
					if(x=='X')
						a[i][j].r=-2 , a[i][j].j=-2;
					else
						a[i][j].r=-1 , a[i][j].j=-1;
		}
	for(int i=1;i<=N;i++)
		a[i][0].r=-2 ,a[i][0].j=-2, a[i][M+1].r=-2 , a[i][M+1].j=-2;
	for(int j=1;j<=M;j++)
		a[0][j].r=-2 , a[0][j].j=-2 , a[N+1][j].r=-2 , a[N+1][j].j=-2;
}
void lee();
int main()
{	citire();
	lee();
	f.close();
	g.close();
	return 0;
}
void lee()
{	int i,j,xx,yy,ii,jj;
	while(!ro.empty())
	{	xx=ro.front().first , yy=ro.front().second , ro.pop();
		for(i=0;i<8;i++)
		{	ii=xx+dx[i] , jj=yy+dy[i];
			if(a[ii][jj].r==-1)
				a[ii][jj].r=a[xx][yy].r+1 , ro.push(make_pair(ii,jj));
		}
	}
	while(!jul.empty())
	{	xx=jul.front().first , yy=jul.front().second , jul.pop();
		for(i=0;i<8;i++)
		{	ii=xx+dx[i] , jj=yy+dy[i];
			if(a[ii][jj].j==-1)
				a[ii][jj].j=a[xx][yy].j+1 , jul.push(make_pair(ii,jj));
		}
	}
	min1.tmin=100000;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			if(a[i][j].r==a[i][j].j&&a[i][j].r!=-1&&a[i][j].r!=-2)
				if(min1.tmin>a[i][j].r)
					min1.i=i , min1.j=j , min1.tmin=a[i][j].r;
	g<<min1.tmin<<" "<<min1.i<<" "<<min1.j;
}