Cod sursa(job #378239)

Utilizator acelasi7Tudor Maxim acelasi7 Data 27 decembrie 2009 23:13:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
#include<string>
using namespace std;
const int dx[]={0,-1,-1,-1,0,1,1,1,0};
const int dy[]={0,-1,0,1,1,1,0,-1,-1};
int a[150][150];
int n,m,iJ,jJ,iR,jR,minn,im,jm;
int coadai[10002],coadaj[10002];
void citire()
{
	char x;
	int i,j;
	ifstream in("rj.in");
	in>>n>>m;
	in.get();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			in.get(x);
			if(x=='J')
			{
				iJ=i;
				jJ=j;
			}
			else if(x=='R')
			{
				iR=i;
				jR=j;
			}
			else if(x=='X')
				a[i][j]=-1;
		}
		in.get();
	}
	for(i=0;i<=n+1;i++)
		a[i][0]=a[i][m+1]=-1;
	for(j=1;j<=m;j++)
		a[0][j]=a[n+1][j]=-1;
	in.close();
}
void lee1()
{
	int pi,pf,k,x,y,i,j;
	pi=0;
	pf=1;
	coadai[pi]=iJ;
	coadaj[pi]=jJ;
	a[iJ][jJ]=1;
	while(pi<pf)
	{
		i=coadai[pi];
		j=coadaj[pi];
		for(k=1;k<=8;k++)
		{
			x=i+dx[k];
			y=j+dy[k];
			if(a[x][y]==0||(a[x][y]>=a[i][j]+1&&a[x][y]!=-1))
			{
				a[x][y]=a[i][j]+1;
				coadai[pf]=x;
				coadaj[pf]=y;
				pf++;
			}
		}
		pi++;
	}
}
/*void drum(int i,int j)
{
	int x,y,k;
	if(a[i][j]==minn)
	{
		im=i;
		jm=j;
	}
	else if(a[i][j]>minn)
	{
		for(k=1;k<=8;k++)
		{
			x=i+dx[k];
			y=j+dy[k];
			if(a[x][y]+1==a[i][j])
				drum(x,y);
		}
	}
}*/
void drum(int i,int j)
{
	int x,y,k;
	while(a[i][j]>minn)
	{
		for(k=1;k<=8;k++)
		{
			x=i+dx[k];
			y=j+dy[k];
			if(a[i][j]==a[x][y]+1)
			{
				k=10;
				i=x;
				j=y;
			}
		}
	}
	if(a[i][j]==minn)
	{
		im=i;
		jm=j;
	}
}
int main()
{
	ofstream out("rj.out");
	citire();
	lee1();
	minn=(a[iR][jR]/2)+1;
	drum(iR,jR);
	out<<minn<<" "<<im<<" "<<jm<<'\n';
	out.close();
	return 0;
}