Cod sursa(job #613159)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 17 septembrie 2011 11:03:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

int n,m,romeo[105][105],ju[105][105];
int xx[]={-1,-1,-1,0,1,1,1,0};
int yy[]={-1,0,1,1,1,0,-1,-1};
char t[105][105];
pair <int, int> pr,pj,final;

void full(int sz[105][105])
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			sz[i][j]=n*m;
		
}
void lee(int sz[105][105],int x,int y)
{

	int k,i,j;
	queue < pair<int, int> > q;
	q.push(make_pair(x,y));
	sz[x][y]=0;
	while(q.size()>0)
	{
		x=q.front().first;
		y=q.front().second;
		q.pop();
		for(k=0;k<8;k++)
		{
			i=x+xx[k];
			j=y+yy[k];
			if(i>=0 && i<n && j>=0 && j<m && t[i][j]!='X' && sz[i][j]==n*m)
			{
				sz[i][j]=sz[x][y]+1;
				q.push(make_pair(i,j));
			}
		}
	}


}


int main()
{	
	int i,j;
	freopen("rj.in","r", stdin);
	scanf("%d %d\n",&n,&m);
	for(i=0;i<n;i++) fgets(t[i],105, stdin);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(t[i][j]=='R') //pr.first=i; pr.second=j;
				pr=make_pair(i,j);
			if(t[i][j]=='J')
				pj=make_pair(i,j);
		
		}
	full(romeo);
	full(ju);
	lee(romeo,pr.first,pr.second);
	lee(ju,pj.first,pj.second);
	int min=n*m;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(romeo[i][j]==ju[i][j] && romeo[i][j]<min) { min=romeo[i][j]; final=make_pair(i,j); }
		}
	freopen("rj.out","w", stdout);
	printf("%d %d %d",min+1,final.first+1,final.second+1);
	
	return 0;
}