Cod sursa(job #1140501)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 12 martie 2014 01:47:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;

bool vizr[102][102],vizj[102][102];
int matr[102][102];
int n,m,x,y;
char c;
int xr,yr,xj,yj;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
pair<int,int> aux,aux1;
bool ok(int x, int y)
{
	return (x>=1 && y>=1 && x<=n && y<=m ) ;
}
int parg(int xr,int yr, int xj, int yj)
{
	queue< pair<int, int> > R;
	R.push(make_pair(xr,yr));
	vizr[xr][yr]=1;
	while(!R.empty())
	{
		aux=R.front();
		for(int k=0;k<8;k++)
		{
			int ll=aux.first+dl[k]; int cc=aux.second+dc[k];
			if( !vizr[ll][cc] && matr[ll][cc]>=0 && ok(ll,cc) )
			{
				R.push( make_pair(ll,cc) );
				vizr[ll][cc]=1;
				matr[ll][cc]=matr[aux.first][aux.second]+1;
			}
			if( ll==xj && cc==yj ) return matr[ll][cc]/2+1;
		}
		R.pop();
	}
}
void drum(int xx, int yy, int rez)
{
	queue< pair<int,int> > Q;
	Q.push( make_pair(xx,yy) );
	while(!Q.empty())
	{
		aux=Q.front();
		if(matr[aux.first][aux.second]==rez) 
		{
			x=aux.first;
			y=aux.second;
			return;
		}
		for(int k=0;k<8;k++)
		if( matr[aux.first+dl[k]][aux.second+dc[k]]  == matr[aux.first][aux.second]-1) 
		{
			Q.push( make_pair(aux.first+dl[k],aux.second+dc[k]) );
		}
		Q.pop();
	}
}
int main()
{
	freopen("rj.in","rt",stdin);
	freopen("rj.out","wt",stdout);
	scanf("%d%d%c",&n,&m,&c);
	for(register int i=1;i<=n;i++,scanf("%c",&c))
		for(register int j=1;j<=m;j++)
		{
			scanf("%c",&c);
			if(c=='X') matr[i][j]=-1;
			if(c=='R') {xr=i; yr=j;}
			if(c=='J') {xj=i; yj=j;}
		}
	int rez=parg(xr,yr,xj,yj);
	drum(xj,yj,rez-1);
	printf("%d %d %d\n",rez,x,y);
	return 0;
}