Cod sursa(job #547550)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 6 martie 2011 14:33:30
Problema Rj Scor 100
Compilator cpp Status done
Runda preg1 Marime 1.8 kb
#include<cstdio>
#include<utility>
#include<deque>
using namespace std;
void read(),solve(),bfr(),bfj();
deque<pair<int,int> > Q;
char A[110],aux[3];
int R[110][110],xj,yj,xr,yr,minim=11000,mini,minj,i,j,n,m,costr[110][110],costj[110][110],dx[]={1,1,1,0,0,-1,-1,-1},dy[]={-1,0,1,-1,1,-1,0,1},N,M;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d",&n,&m);
	fgets(aux,3,stdin);
	for(i=1;i<=n;i++)
	{
		fgets(A+1,105,stdin);
		for(j=1;j<=m;j++)
		{
			costr[i][j]=costj[i][j]=-1;
			if(A[j]=='R'){xr=i;yr=j;}
			if(A[j]=='J'){xj=i;yj=j;}
			if(A[j]=='X'){R[i][j]=0;continue;}
			R[i][j]=1;
		}
	}
	for(i=0;i<=n+1;i++){R[i][0]=R[i][m+1]=0;costr[i][0]=costr[i][m+1]=costj[i][0]=costj[i][m+1]=-1;}

	for(i=0;i<=m+1;i++){R[0][i]=R[n+1][i]=0;costr[0][i]=costr[n+1][i]=costj[0][i]=costj[n+1][i]=-1;}
}
void solve()
{
	bfr();
	bfj();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(costr[i][j]==costj[i][j])
				if(costr[i][j]<minim&&costr[i][j]!=-1){minim=costr[i][j];mini=i;minj=j;}
	printf("%d %d %d",minim,mini,minj);
}
void bfr()
{
	Q.push_back(make_pair(xr,yr));
	costr[xr][yr]=1;
	for(;!Q.empty();)
	{
		N=Q.front().first;
		M=Q.front().second;
		for(i=0;i<8;i++)
			if(R[N+dx[i]][M+dy[i]]&&costr[N+dx[i]][M+dy[i]]==-1)
			{
				costr[N+dx[i]][M+dy[i]]=costr[N][M]+1;
				Q.push_back(make_pair(N+dx[i],M+dy[i]));
			}
		Q.pop_front();
	}
}
void bfj()
{
	Q.resize(0);
    Q.push_back(make_pair(xj,yj));
	costj[xj][yj]=1;
	for(;!Q.empty();)
	{
		N=Q.front().first;
		M=Q.front().second;
		for(i=0;i<8;i++)
			if(R[N+dx[i]][M+dy[i]]&&costj[N+dx[i]][M+dy[i]]==-1)
			{
				costj[N+dx[i]][M+dy[i]]=costj[N][M]+1;
				Q.push_back(make_pair(N+dx[i],M+dy[i]));
			}
		Q.pop_front();
	}
}