Cod sursa(job #614647)

Utilizator marianfFocsa Marian marianf Data 6 octombrie 2011 23:08:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
using namespace std;

int a[105][105],b[105][105],N,M,xr,yr,xj,yj,pozi,pozj,dist;
bool c[105][105];
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;c[i][j+1]=true;}
			else if(s[j]=='R') 
			{
				xr=i;
				yr=j+1;
				c[i][j+1]=true;
			}
			else 
			{
				xj=i;
				yj=j+1;
				c[i][j+1]=true;
			}
		}
	}
	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,x,y;
	
	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++)
		{
			x=i+dx[k];
			y=j+dy[k];
			if(a[x][y]==0 && c[x][y]==false)
			{
				ul++;
				q[ul].x=x;
				q[ul].y=y;
				a[x][y]=a[i][j]+1;
				c[x][y]=true;
			}
		}
	}
}

void Julieta()
{
	int pr=0,ul=-1,i,j,x,y,k;
	
	
	for(i=0;i<=N+1;i++)
		for(j=0;j<=M+1;j++)
		{
			if(b[i][j]==1) c[i][j]=true;
			else c[i][j]=false;
		}
	c[xr][yr]=c[xj][yj]=true;
	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++)
		{
			x=i+dx[k];
			y=j+dy[k];
			if(b[x][y]==0 && c[x][y]==false)
 			{
				ul++;
				q[ul].x=x;
				q[ul].y=y;
				b[x][y]=b[i][j]+1;
				c[x][y]=true;
			}
		}
	}
}

void Comparare()
{
	int i,j;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			if(a[i][j]!=1 && a[i][j]!=0 && b[i][j]!=1 && b[i][j]!=0 && a[i][j]==b[i][j])
			{
				dist=a[i][j]+1;
				pozi=i;
				pozj=j;
			}
}

void Afisare()
{
	ofstream fout("rj.out");
	fout<<dist<<" "<<pozi<<" "<<pozj<<"\n";
	fout.close();
}


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