Cod sursa(job #573687)

Utilizator t2011tVasilescu Popescu t2011t Data 6 aprilie 2011 14:59:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>
#include <queue>
#include <utility>
using namespace std;

int i,n,m,yr,xr,yj,xj,v[2][120][102]; //v[1] - R, v[2] - J
int dy[4]={1,-1,0,0},dx[4]={0,0,1,-1};
char c;
int ymin,xmin,tmin=10001;

queue <pair <int,int> > yx;

void lee();

int main()
{
FILE *in,*out;
in=fopen("rj.in","rt");
out=fopen("rj.out","wt");

//citirea
fscanf(in,"%d%d",&n,&m);
fscanf(in,"%c",&c);

int i1,i2;

for(i1=1;i1<=n;i1++)
	{
	for(i2=1;i2<=m;i2++)
		{
		fscanf(in,"%c",&c);
		switch(c)
			{
			case 'X' : {v[1][i1][i2]=-1; v[2][i1][i2]=-1; break;}
			case 'R' : {yr=i1; xr=i2; break;}
			case 'J' : {yj=i1; xj=i2; break;}
			}
		}
	fscanf(in,"%c",&c);
	}
v[1][yr][xr]=1;
v[2][yj][xj]=1;
//

//bordarea
for(i1=0;i1<=n+1;i1++)
	{
	v[1][i1][0]=-1; v[2][i1][0]=-1;
	v[1][i1][m+1]=-1; v[2][i1][m+1]=-1;
	}
for(i1=0;i1<=m+1;i1++)
	{
	v[1][0][i1]=-1; v[2][0][i1]=-1; 
	v[1][n+1][i1]=-1; v[2][n+1][i1]=-1;
	}
//


//R
yx.push( make_pair(yr,xr));
i=1;
lee();
//
//J
yx.push( make_pair(yj,xj));
i=2;
lee();
//

//coord + tmin
for(i1=1;i1<=n;i1++)
	for(i2=1;i2<=m;i2++)
		{
		if(v[1][i1][i2] != -1)
			if(v[1][i1][i2] == v[2][i1][i2])
				if(v[1][i1][i2] < tmin)
					{
					ymin=i1; xmin=i2;
					tmin=v[1][i1][i2];
					}
		}
//

fprintf(out,"%d %d %d",ymin,xmin,tmin-1);

fclose(in);
fclose(out);
return 0;
}

void lee()
{
int i1;
bool sw;

while(!yx.empty())
	{
	for(i1=0;i1<4;i1++)
		{
		sw=false;
			
		if(!v[i][yx.front().first+dy[i1]][yx.front().second+dx[i1]])
			sw=true;
		else
		if(v[i][yx.front().first+dy[i1]][yx.front().second+dx[i1]] > v[i][yx.front().first][yx.front().second]+1)
			sw=true;
		if(sw)
			{
			v[i][yx.front().first+dy[i1]][yx.front().second+dx[i1]] = v[i][yx.front().first][yx.front().second]+1;
			yx.push(make_pair(yx.front().first+dy[i1],yx.front().second+dx[i1]));
			}
		}
	yx.pop();
	}
}