Cod sursa(job #1140491)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 12 martie 2014 01:13:19
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 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,J;
	int nrr=0, nrj=0;
	R.push(make_pair(xr,yr));
	J.push(make_pair(xj,yj));
	vizr[xr][yr]=1;
	vizj[xj][yj]=1;
	while(!R.empty() && !J.empty())
	{
		aux=R.front();
		while(nrr == matr[aux.first][aux.second])
		{
			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;
				}
			}
			R.pop(); aux=R.front();
		}
		nrr++;
		
		aux=J.front();
		while(nrj == matr[aux.first][aux.second])
		{
			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]==nrj+1 ) 
				{
					x=ll;
					y=cc;
					return matr[aux.first][aux.second]+2;
				}
				if( !vizj[ll][cc] && matr[ll][cc]>=0 && ok(ll,cc) )
				{
					J.push( make_pair(ll,cc) );
					vizj[ll][cc]=1;
					matr[ll][cc]=matr[aux.first][aux.second]+1;
				}			
			}
			J.pop(); aux=J.front();
		}
		nrj++;
	}
	
}
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);
	printf("%d %d %d\n",rez,x,y);
	return 0;
}