Cod sursa(job #337670)

Utilizator Abi79Iordache Albert Abi79 Data 4 august 2009 15:38:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <queue>

using namespace std;

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

void BFS()
{
	c.x=x; c.y=y;
	q.push(c);
	
	while(q.size())
	{
		d=q.front();
		q.pop();
		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 && a[c.x][c.y]>=0 && ( (a[d.x][d.y]+1) < a[c.x][c.y] || a[c.x][c.y]==0) )
			{
				q.push(c);
				a[c.x][c.y]=a[d.x][d.y]+1;
			}
		}
	}
	
	c.x=x2; c.y=y2;
	a[x2][y2]*=(-1);
	
	q.push(c);
	
	while(1)
	{
		d=q.front();
		if(-a[d.x][d.y]!=(-a[x2][y2])/2+1 && a[d.x][d.y]!=(-a[x2][y2])/2+1)
			q.pop();
		else
			break;
		for(i=0;i<8;i++)
		{
			c=d;
			c.x+=v[i].x; c.y+=v[i].y;
			if(a[c.x][c.y]==-a[d.x][d.y]-1)
			{
				q.push(c);
				a[c.x][c.y]*=-1;
			}
		}
	}
	
	printf("\n\na[54][10]=%d ",a[54][10]);
	
	rez=q.front();
	while(q.size())
	{
		c=q.front();
		printf("a[%d][%d]=%d ",c.x,c.y,-a[c.x][c.y]);
		if(c.x<rez.x || (c.x==rez.x && c.y<rez.y) )
			rez=c;
		q.pop();
	}
}

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': a[i][j]=1; x=i; y=j; break;
				case 'J': x2=i; y2=j; break;
				case 'X': a[i][j]=-1; break;
				case ' ': a[i][j]=0;  break;
			}
		}
		fscanf(f,"%c");
	}
	
	BFS();
	
	fprintf(s,"%d ",(-a[x2][y2])/2+1);
	
	fprintf(s,"%d %d",rez.x,rez.y);
	
	fclose(s);
	
	return 0;
}