Cod sursa(job #405972)

Utilizator lucianvnDragomir Lucian lucianvn Data 1 martie 2010 00:11:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<fstream>
#define MAX 100002
using namespace std;
struct coada
{
	int x,y;
} pozR, pozJ,c[MAX],a,b;
int i,j,n,m,v[104][104];
char linie[104];
void citire()
{
	ifstream intrare("rj.in");
	intrare>>n>>m;
	for(i=1;i<=n;i++)
	{
		intrare.get();
		intrare.get(linie+1,104);
		for(j=1;j<=m;j++)
		{
			if(linie[j]=='X')
				v[i][j]=-1;
			else if(linie[j]=='R')
			{
				pozR.x=i;
				pozR.y=j;
			}
			else if(linie[j]=='J')
			{
				pozJ.x=i;
				pozJ.y=j;
			}
		}
	}
	intrare.close();
	//ofstream iesire("rj.out");
	for(i=0;i<=n+1;i++)
	{
		v[i][0]=-1;
		v[i][m+1]=-1;
	}
	for(i=1;i<=m;i++)
	{
		v[0][i]=-1;
		v[n+1][i]=-1;
	}
/*	for(i=1;i<n+1;i++)
	{
		for(j=1;j<m+1;j++)
		{
			if(v[i][j]==0) iesire<<" ";
			iesire<<v[i][j]<<" ";
		}
			iesire<<"\n";
	}*/
}
int dl[]={0,1,1,1,0,-1,-1,-1};
int dc[]={1,1,0,-1,-1,-1,0,1};
int pasiR[104][104],pasiJ[104][104];
void leeR()
{
	int p=0,u=0;
	c[p]=pozR;
	while(p<=u)
	{
		a=c[p++];
		for(i=0;i<8;i++)
		{
			b.x=a.x+dl[i];
			b.y=a.y+dc[i];
			if(v[b.x][b.y]==0 && pasiR[b.x][b.y]==0)
			{
				pasiR[b.x][b.y]=pasiR[a.x][a.y]+1;
				c[++u]=b;
			}
		}
	}
}
void leeJ()
{
	int p=0,u=0;
	c[p]=pozJ;
	while(p<=u)
	{
		a=c[p++];
		for(i=0;i<8;i++)
		{
			b.x=a.x+dl[i];
			b.y=a.y+dc[i];
			if(v[b.x][b.y]==0 && pasiJ[b.x][b.y]==0)
			{
				pasiJ[b.x][b.y]=pasiJ[a.x][a.y]+1;
				c[++u]=b;
			}
		}
	}
}
void verifica()
{
	int min=1000000;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(pasiJ[i][j]==pasiR[i][j] && pasiJ[i][j]!=0 && min>pasiR[i][j])
			{
				min=pasiR[i][j];
				pozR.x=i;
				pozR.y=j;
			}
		}
	}
	ofstream iesire("rj.out");
	iesire<<min+1<<" "<<pozR.x<<" "<<pozR.y;
	iesire.close();
}
int main()
{
	citire();
	leeR();
	leeJ();
	verifica();
	return 0;
}