Cod sursa(job #615036)

Utilizator suzanicaSuzanica Mihu suzanica Data 8 octombrie 2011 13:25:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
using namespace std;

unsigned int i,j,n,m,yr,xr,xj,yj,r[102][102],jj[102][102];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int min1,p1,p2;
char a[102][102],x;
void rezolva(int x,int y,unsigned int p[102][102])
{
	int xx,yy,ok=1,i,j,k;
	for(i=0;i<=n+1;i++)
		for(j=0;j<=m+1;j++)
			p[i][j]=10000;
		p[x][y]=1;
		while(ok)
		{
			ok=0;
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
					for(k=0;k<8;k++)
					{
						xx=i+dx[k];
						yy=j+dy[k];
					if(a[xx][yy]!='X'&&p[i][j]+1<p[xx][yy])
					{
						p[xx][yy]=p[i][j]+1;
						ok=1;
					}
					}
		}
}
int main()
{
	ifstream f("rj.in");
	ofstream g("rj.out");
	f>>n>>m;
	f.get(x);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f.get(x);
			a[i][j]=x;
			if(a[i][j]=='R')
			{
				xr=i;
				yr=j;
			}
			if(a[i][j]=='J')
			{
				xj=i;
				yj=j;
			}
		}
		f.get(x);
	}
	for(i=0;i<=m+1;i++)
		a[0][i]=a[n+1][i]='X';
	for(j=0;j<=n+1;j++)
		a[j][0]=a[j][m+1]='X';
	rezolva(xr,yr,r);
	rezolva(xj,yj,jj);
	min1=10000;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(r[i][j]==jj[i][j]&&r[i][j]<min1)
			{
				min1=r[i][j];
				p1=i;
				p2=j;
			}
		g<<min1<<" "<<p1<<" "<<p2;
	return 0;
}