Cod sursa(job #356257)

Utilizator funkydvdIancu David Traian funkydvd Data 13 octombrie 2009 22:49:23
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream f1 ("rj.in");
ofstream f2 ("rj.out");
int b[103][103], c[103][103],n,m;
char s;
struct rj {int x, y;};
rj ro,jul;
deque<rj> q;
void citire()
{
	f1>>n>>m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
		{
			f1>>s;
			if (s=='X') b[i][j]=c[i][j]=-1;
			else if (s=='R') 
			{
				ro.x=i;
				ro.y=j;
			}
			else if (s=='J') 
			{
				jul.x=i;
				jul.y=j;
			}
		}
	b[ro.x][ro.y]=c[jul.x][jul.y]=1;
}

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

void mark (rj y, int D[103][103])
{
	const int dlin[]={-1,-1,-1,0,0,1,1,1}, dcol[]={-1,0,1,-1,1,-1,0,1};
	rj z;
	for (int i=1; i<=8; i++)
		if (D[y.x+dlin[i]][y.y+dcol[i]]==0)
		{								
			z.x=y.x+dlin[i];
			z.y=y.y+dcol[i];
			q.push_back(z);
			D[z.x][z.y]=D[y.x][y.y]+1;
		}
}

void bfs (rj x, int p[103][103])
{
	q.push_back(x);
	while (!q.empty())
		mark (q.front(), p);
	q.pop_front();
}


void afisare()
{
	int min=100000;
	rj rez;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			if (b[i][j]==c[i][j] && b[i][j]<min)
			{
				min=b[i][j];
				rez.x=i;
				rez.y=j;
			}
	f2<<min<<" "<<rez.x<<" "<<rez.y;
}
int main()
{		 
	citire();
	bordare();
	bfs (ro, b);
	bfs (jul,c);
	afisare();
	return 0;		
}