Cod sursa(job #559146)

Utilizator MacaMacarescu Alexandru Maca Data 17 martie 2011 17:09:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
#include<queue>
#include<iomanip>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int R[130][130],N,M,J[130][130];
int rx,ry,jx,jy;
struct nod
{	int x,y;
};
queue<nod>q;
nod mp(int x,int y)
{	nod a;
	a.x=x , a.y=y;
	return a;
}
void bfs()
{	int x,y,xx,yy,i;
	q.push(mp(rx,ry));
	R[rx][ry]=1;
	while(!q.empty())
	{	x=q.front().x;
		y=q.front().y;
		q.pop();
		for(i=0;i<8;i++)
		{	xx=x+dx[i];
			yy=y+dy[i];
			if(R[xx][yy]==-1)
				continue;
			if(R[xx][yy]==0)
				R[xx][yy]=R[x][y]+1 , q.push(mp(xx,yy));
		}
	}
	J[jx][jy]=1;
	q.push(mp(jx,jy));
	while(!q.empty())
	{	x=q.front().x;
		y=q.front().y;
		q.pop();
		for(i=0;i<8;i++)
		{	xx=x+dx[i];
			yy=y+dy[i];
			if(J[xx][yy]==-1)
				continue;
			if(J[xx][yy]==0)
				J[xx][yy]=J[x][y]+1 , q.push(mp(xx,yy));
		}
	}
}	
int main()
{	int i,j,xf,yf,min=1000,y;
	char x;
	in>>N>>M;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
		{	in>>noskipws>>x;
			if(j==1 && x=='\n')
				in>>noskipws>>x;
			if(x=='R')
				rx=i , ry=j;
			if(x=='J')
				jx=i , jy=j;
			if(x=='X')
				R[i][j]=J[i][j]=-1;			
		}
	for(i=0;i<=M+1;i++)
		R[N+1][i]=J[N+1][i]=R[0][i]=J[0][i]=-1;
	for(j=0;j<=N+1;j++)
		R[j][M+1]=J[j][M+1]=R[j][0]=J[j][0]=-1;
	bfs();	
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			if(R[i][j]==J[i][j] && R[i][j]!=-1 && min>R[i][j] && R[i][j])
			{	min=R[i][j];
				xf=i;
				yf=j;
			}
	out<<min<<" "<<xf<<" "<<yf;
	in.close();
	out.close();
	return 0;
}