Cod sursa(job #573307)

Utilizator mihai995mihai995 mihai995 Data 6 aprilie 2011 10:04:31
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
using namespace std;

const int N=150,dl[]={-1,-1,0,1,1,1,0,-1},dc[]={0,1,1,1,0,-1,-1,-1};
struct punct{int x,y;} c[N*N];
int a[N][N],b[N][N],n,m,st,dr;
char s[N][N];

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

void proc(int v[][N],punct x)
{
	punct y;
	for (int i=0;i<8;i++)
	{
		y.x=x.x+dl[i];
		y.y=x.y+dc[i];
		if (s[y.x][y.y]==' ' && !v[y.x][y.y])
		{
			v[y.x][y.y]=v[x.x][x.y]+1;
			c[++dr]=y;
		}
	}
}

void dfs(int v[][N],punct x)
{
	st=dr=0;
	v[x.x][x.y]=1;
	c[++dr]=x;
	while (st<=dr)
		proc(v,c[++st]);
}

int main()
{
	int i,j,x,y;
	punct R,J;
	in>>n>>m>>ws;
	for (i=1;i<=n;i++)
		in.getline(s[i]+1,m+1);
	for (i=0;i<=n+1;i++)
		s[i][0]=s[i][m+1]='X';
	for (i=0;i<=m+1;i++)
		s[0][i]=s[n+1][i]='X';
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			if (s[i][j]=='R')
			{
				R.x=i;
				R.y=j;
			}
			if (s[i][j]=='J')
			{
				J.x=i;
				J.y=j;
			}
		}
	dfs(a,R);
	dfs(b,J);
	a[0][0]=1<<30;
	x=y=0;
	for (j=m;j;j--)
		for (i=n;i;i--)
			if (a[i][j] && a[i][j]==b[i][j] && a[i][j]<a[x][y])
			{
				x=i;
				y=j;
			}
	out<<a[x][y]<<" "<<x<<" "<<y<<"\n";
	return 0;
}