Cod sursa(job #749168)

Utilizator svladScurtu Vlad svlad Data 15 mai 2012 23:06:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
using namespace std;
int a[105][105],b[105][105];
typedef struct {int x,y;} PUNCT;
PUNCT e[10005],d[10005];
int main()
{
	ifstream f("rj.in");
	ofstream g("rj.out");
	int dx[8]={1,-1,0,0,1,1,-1,-1};
	int dy[8]={0,0,-1,1,-1,1,-1,1};
	int n,m,i,j,p=1,u=1,x1,y1,x2,y2,min;
	char c;
	f>>n; f>>m;
	for(i=0;i<=m;i++) {a[n+1][i]=-1; b[n+1][i]=-1; a[0][i]=-1; a[0][i]=-1;}
	for(i=0;i<=n;i++) {a[i][0]=-1; b[i][0]=-1; a[i][m+1]=-1; b[i][m+1]=-1;}
	f.get(c);
	for(i=1;i<=n;i++)
	{	for(j=1;j<=m;j++)
		{ f.get(c);
		  if(c=='R') {a[i][j]=0; b[i][j]=0; d[u].x=i; d[u].y=j;}
		  if(c=='J') {a[i][j]=0; b[i][j]=0; e[u].x=i; e[u].y=j;}
		  if(c==' ') {a[i][j]=1000; b[i][j]=1000;}
		  if(c=='X') {a[i][j]=-1; b[i][j]=-1;}
		}
		while(c!='\n'&&i!=n) f.get(c);
	}
	p=u=1;
	while(p<=u)
	{	x1=d[p].x;
		y1=d[p].y;
		for(i=0;i<=7;i++)
		{	if(a[x1][y1]+1<a[x1+dx[i]][y1+dy[i]])
			 { 
				a[x1+dx[i]][y1+dy[i]]=a[x1][y1]+1;
				u++;
				d[u].x=x1+dx[i];
				d[u].y=y1+dy[i];
			 }
		}
		p++;
	}
	p=u=1;
	while(p<=u)
	{	x1=e[p].x;
		y1=e[p].y;
		for(i=0;i<=7;i++)
		{	if(b[x1][y1]+1<b[x1+dx[i]][y1+dy[i]])
			 { 
				b[x1+dx[i]][y1+dy[i]]=b[x1][y1]+1;
				u++;
				e[u].x=x1+dx[i];
				e[u].y=y1+dy[i];
			 }
		}
		p++;
	}
	min=9999;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=m;j++)
		 { if(a[i][j]==b[i][j]&&min>b[i][j]&&b[i][j]!=-1&&b[i][j]!=0)
			 { min=a[i][j]; x1=i; x2=j;}
		 }
	}
	g<<min+1<<" "<<x1<<" "<<x2;
	f.close();
	g.close();
	return 0;
}