Cod sursa(job #418560)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 16 martie 2010 01:55:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<cstdio>
#include<algorithm>
#include<queue>
#define ff first
#define ss second
using namespace std;
int i,j,n,m,a[105][105],b[105][105],c[105][105],xR,yR,xJ,yJ,sol;
int dx[]={0, 0,1, 1,1,-1,-1,-1};
int dy[]={1,-1,0,-1,1, 0, 1,-1};
queue<pair<int,int> > QR,QJ;
void read(),solve(),show();
int main()
{
	read();
	solve();
	show();
	return 0;
}
void read()
{
	char x;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d%c",&n,&m,&x);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%c",&x);
			if(x==' ')a[i][j]=0;
			else if(x=='X')a[i][j]=1;
			else if(x=='R')xR=i,yR=j;
			else if(x=='J')xJ=i,yJ=j;
		}
		scanf("%c",&x);
	}
	for(i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=1;
	for(j=0;j<=m+1;j++) a[0][j]=a[n+1][j]=1;
}
void solve()
{
	pair<int,int> curr;
	sol=-1;
	QR.push(make_pair(xR,yR)); b[xR][yR]=1;
	QJ.push(make_pair(xJ,yJ)); c[xJ][yJ]=1;
	while(QR.size() || QJ.size())
	{
		//il verificam pe Romeo
		curr=QR.front(); 
		for(i=0;i<8;i++) //pentru fiecare directie verificam daca e liber si adaugam la coada
			if(!a[curr.ff+dx[i]][curr.ss+dy[i]] && !b[curr.ff+dx[i]][curr.ss+dy[i]])
			{
				b[curr.ff+dx[i]][curr.ss+dy[i]]=b[curr.ff][curr.ss]+1;
				QR.push(make_pair(curr.ff+dx[i],curr.ss+dy[i]));
			}
		QR.pop();
		//o verificam pe Julieta
		curr=QJ.front(); 
		for(i=0;i<8;i++) //pentru fiecare directie verificam daca e liber si adaugam la coada
			if(!a[curr.ff+dx[i]][curr.ss+dy[i]] && !c[curr.ff+dx[i]][curr.ss+dy[i]])
			{
				c[curr.ff+dx[i]][curr.ss+dy[i]]=c[curr.ff][curr.ss]+1;
				QJ.push(make_pair(curr.ff+dx[i],curr.ss+dy[i]));
			}
		QJ.pop();
	}
}

void show()
{
	//cautam cea mai mica si mai buna solutie :D
	sol=m*n+10;
	xR=1,yR=1;
	for(i=0;i<=n;i++)
		for(j=0;j<=m;j++)
			if(b[i][j]==c[i][j] && b[i][j] && c[i][j] && sol > b[i][j])
				sol=b[i][j],xR=i,yR=j;
	printf("%d %d %d\n",sol,xR,yR);
}