Cod sursa(job #614721)

Utilizator marianfFocsa Marian marianf Data 7 octombrie 2011 16:07:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
using namespace std;

int a[200][200],b[200][200],n,m,rom1,rom2,jul1,jul2,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
{
	int x,y;
};
coord q[10000];

void Citire()
{
	int i,j;
	char s[200];
	ifstream fin("rj.in");
	fin>>n>>m;
	fin.get();
	for(i=1;i<=n;i++)
	{
		fin.getline(s,200);
		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') 
			{
				rom1=i;
				rom2=j+1;
			}
			else 
			{
				jul1=i;
				jul2=j+1;
			}
		}
	}
	fin.close();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			b[i][j]=a[i][j];
}


void Bordare()
{
	int i;
	for(i=0;i<=m+1;i++)
	{
		a[0][i]=a[n+1][i]=-1;
		b[0][i]=b[n+1][i]=-1;
	}
	for(i=0;i<=n+1;i++)
	{
		a[i][0]=a[i][m+1]=-1;
		b[i][0]=b[i][m+1]=-1;
	}
}

void Romeo()
{
	int pr=0,ul=-1,i,j,k,lin,col;
	a[rom1][rom2]=2;
	
	ul++;
	q[ul].x=rom1;
	q[ul].y=rom2;
	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[jul1][jul2]=2;
	
	ul++;
	q[ul].x=jul1;
	q[ul].y=jul2;
	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;
}