Cod sursa(job #78431)

Utilizator gigi_becaliGigi Becali gigi_becali Data 17 august 2007 19:15:08
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <string>
#define maxn 101
#include <queue>
using namespace std;

char x[maxn][maxn];
bool viz[maxn][maxn];
int n, m;
struct nod { int i, j;nod(){}; nod(int a, int b){i=a; j=b;};};
const int xx[9]={-1,-1,0,1,1,1 ,0 ,-1};
const int yy[9]={ 0, 1,1,1,0,-1,-1,-1};
short dr[maxn][maxn], dj[maxn][maxn];
nod r, J;
void read()
{
	freopen("rj.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	int i;
	for(i=0;i<n;++i) gets(x[i]);
}

void bfsr(nod s)
{
	queue<nod>Q;
	Q.push(s);
	int i, newi, newj;
	nod u;
	memset(viz, 0,sizeof(viz));
	viz[s.i][s.j]=1;
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
	//	printf("%d %d\n", u.i, u.j);
		for(i=0;i<8;++i)
		{
			newi=u.i+xx[i];
			newj=u.j+yy[i];
		//	printf("%d %d\n", newi, newj);
			if(newi>=0 && newi<n && newj>=0 && newj<m)
				if(x[newi][newj]!='X' && !viz[newi][newj])
				{
					dr[newi][newj]=dr[u.i][u.j]+1;
					viz[newi][newj]=1;
					Q.push(nod(newi,newj));
				}
		}
	}
	
}

void bfsj(nod s)
{
	queue<nod>Q;
	Q.push(s);
	int i, newi, newj;
	nod u;
	memset(viz, 0,sizeof(viz));
	
	viz[s.i][s.j]=1;
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
		for(i=0;i<8;++i)
		{
			newi=u.i+xx[i];
			newj=u.j+yy[i];
			if(newi>=0 && newi<n && newj>=0 && newj<m)
				if(x[newi][newj]!='X' && !viz[newi][newj])
				{
					dj[newi][newj]=dj[u.i][u.j]+1;
					viz[newi][newj]=1;
					Q.push(nod(newi,newj));
				}
		}
	}
	
}

int main()
{
	read();
	int i, j;
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			if(x[i][j]=='R') r.i=i, r.j=j;
			else if(x[i][j]=='J') J.i=i, J.j=j;
			
	bfsr(r);
	bfsj(J);
		//	printf("\n");
	//for(i=0;i<n;++i)
	{
//		for(j=0;j<m;++j)printf("%d ", dj[i][j]);
	//	printf("\n");
	}

	int min=0x3f3f3f3f, pi=-1, pj=-1;
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			if(x[i][j]==' ')
				if(dr[i][j]==dj[i][j] && dr[i][j])
					if(min>dr[i][j]) min=dr[i][j], pi=i, pj=j;
				
freopen("rj.out","w",stdout);
	printf("%d %d %d\n", min+1, pi+1, pj+1);
	
	return 0;
}