Cod sursa(job #614702)

Utilizator marianfFocsa Marian marianf Data 7 octombrie 2011 15:11:48
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
using namespace std;

int a[105][105],b[105][105],N,M,xr,yr,xj,yj,x,y,tmin;
int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};

struct coord
{
	short x,y;
};
coord q[10000];

void Citire()
{
	int i,j;
	char s[105];
	ifstream fin("rj.in");
	fin>>N>>M;
	fin.get();
	for(i=1;i<=N;i++)
	{
		fin.getline(s,100);
		for(j=0;j<M;j++)
		{
			if(s[j]==' ') a[i][j+1]=0;
			else if(s[j]=='X') a[i][j+1]=1;
			else if(s[j]=='R') 
			{
				xr=i;
				yr=j+1;
			}
			else 
			{
				xj=i;
				yj=j+1;
			}
		}
	}
	fin.close();
}


void Bordare()
{
	int i,j;
	for(i=0;i<=M+1;i++)
		a[0][i]=a[N+1][i]=-1;
	for(i=0;i<=N+1;i++)
		a[i][0]=a[i][M+1]=-1;
	for(i=0;i<=N+1;i++)
		for(j=0;j<=M+1;j++)
			b[i][j]=a[i][j];
}

void Romeo()
{
	int pr=0,ul=-1,i,j,k,lin,col;
	a[xr][yr]=2;
	
	ul++;
	q[ul].x=xr;
	q[ul].y=yr;
	while(pr<=ul)
	{
		i=q[pr].x;
		j=q[pr].y;
		pr++;
		for(k=0;k<8;k++)
		{
			lin=i+dx[k];
			col=j+dy[k];
			if(a[lin][col]==0)
			{
				ul++;
				q[ul].x=lin;
				q[ul].y=col;
				a[lin][col]=a[i][j]+1;
			}
		}
	}
}

void Julieta()
{
	int pr=0,ul=-1,i,j,lin,col,k;
	b[xj][yj]=2;
	
	ul++;
	q[ul].x=xj;
	q[ul].y=yj;
	while(pr<=ul)
	{
		i=q[pr].x;
		j=q[pr].y;
		pr++;
		for(k=0;k<8;k++)
		{
			lin=i+dx[k];
			col=j+dy[k];
			if(b[lin][col]==0)
 			{
				ul++;
				q[ul].x=lin;
				q[ul].y=col;
				b[lin][col]=b[i][j]+1;
			}
		}
	}
}

void Comparare()
{
	int i,j;
	tmin=200000;
	for (i=1;i<=N;i++)
		for (j=1;j<=M;j++)
			if (a[i][j]==b[i][j]&&a[i][j]>1)
				if (tmin>a[i][j]-1)
				{
					tmin=a[i][j]-1;
					x=i;
					y=j;
				}
}

void Afisare()
{
	ofstream fout("rj.out");
	fout<<tmin<<" "<<x<<" "<<y<<"\n";
	fout.close();
}


int main ()
{
	Citire();
	Bordare();
	Romeo();
	Julieta();
	Comparare();
	Afisare();
	return 0;
}