Cod sursa(job #337770)

Utilizator Abi79Iordache Albert Abi79 Data 4 august 2009 22:46:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <queue>

using namespace std;

FILE *f=fopen("rj.in","r"),*s=fopen("rj.out","w");
int n,m,i,j,x[3],y[3],R[101][101],J[101][101];
char ch;
struct Coord{
	int x;
	int y;
};
Coord c,d,rez={102,102},v[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
queue <Coord> q;

void BFS(int address[101][101], int z, int max=0)
{
	c.x=x[z]; c.y=y[z];
	q.push(c);
	
	while(q.size())
	{
		d=q.front();
		q.pop();
		if(address[d.x][d.y]!=max)
		{
			for(i=0;i<8;i++)
			{
				c=d;
				c.x+=v[i].x; c.y+=v[i].y;
				if(c.x>=1 && c.x<=n && c.y>=1 && c.y<=m && address[c.x][c.y]>=0 && ( (address[d.x][d.y]+1) < address[c.x][c.y] || address[c.x][c.y]==0) )
				{
					q.push(c);
					address[c.x][c.y]=address[d.x][d.y]+1;
				}
			}
		}
		else if(R[d.x][d.y]==max && (rez.x>d.x || (rez.x==d.x && rez.y>d.y)) )
			rez=d;
	}
}

int main()
{
	fscanf(f,"%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			fscanf(f,"%c",&ch);
			switch(ch)
			{
				case 'R': R[i][j]=1;  x[1]=i; y[1]=j; break;
				case 'J': J[i][j]=1;  x[2]=i; y[2]=j; break;
				case 'X': R[i][j]=-1; J[i][j]=-1;     break;
				case ' ': R[i][j]=0;  J[i][j]=0;      break;
			}
		}
		fscanf(f,"%c");
	}
	
	BFS(R,1);
	
	BFS(J,2,R[x[2]][y[2]]/2+1);
	
	fprintf(s,"%d %d %d",R[x[2]][y[2]]/2+1,rez.x,rez.y);
	
	fclose(s);
	
	return 0;
}