Cod sursa(job #697181)

Utilizator HoriaClementHoriaC HoriaClement Data 28 februarie 2012 22:54:28
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <queue>

using namespace std;


ifstream in("rj.in");
ofstream out("rj.out");

const int dl[]={-1,-1,-1,0,0,1,1,1};
const int dc[]={-1,0,-1,-1,1,-1,0,1};

int n,m,drom[105][105],djul[105][105];

struct punct
{
	int l,c;
};

queue<punct> q;

punct ro,ju;

char s[105];

void bordare(int a[105][105])
{
	for(int i=0;i<=n+1;++i)
		a[i][0]=a[i][m+1]=-2;
	for(int i=0;i<=m+1;++i)
		a[0][i]=a[n+1][i]=-2;
}
void bfs(int a[105][105],punct x0)
{
	punct x,y;
	q.push(x0);
	a[x0.l][x0.c]=1;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(int i=0;i<=7;++i)
		{
			y.l=x.l+dl[i];
			y.c=x.c+dc[i];
			if(a[y.l][y.c]==-1 || a[y.l][y.c]==0)
			{
				q.push(y);
				a[y.l][y.c]=a[x.l][x.c]+1;
			}
		}
	}
}

void citire()
{
	int j;
	in>>n>>m>>ws;
	for(int i=1;i<=n;++i)
	{
		in.getline(s,105);
		for(j=0;j<m;++j)
		{
			if(s[j]==' ')
				drom[i][j+1]=djul[i][j+1]=-1;
			if(s[j]=='X')
				drom[i][j+1]=djul[i][j+1]=-2;
			if(s[j]=='R')
			{
				drom[i][j+1]=djul[i][j+1]=0;
				ro.l=i;
				ro.c=j+1;
			}
			if(s[j]=='J')
			{
				drom[i][j+1]=djul[i][j+1]=0;
				ju.l=i;
				ju.c=j+1;
			}
		}
	}
	
}

void work()
{
	int t,ti,tj,i,j;
	bordare(djul);bordare(drom);
	bfs(drom,ro),bfs(djul,ju);
	/*for(int i=0;i<=n+1;++i)
	{
		for(int j=0;j<=m+1;++j)
			out<<drom[i][j]<<"\t";
		out<<"\n";
	}
	out<<"\n";*/
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(djul[i][j]==drom[i][j] && t>drom[i][j] && drom[i][j]>0)
			{
				t=drom[i][j];
				ti=i;
				tj=j;
			}
	out<<t<<" "<<ti<<" "<<tj<<"\n";
}

int main()
{
	citire();
	work();
	return 0;
}