Cod sursa(job #337224)

Utilizator Abi79Iordache Albert Abi79 Data 2 august 2009 23:26:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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,maxim=2;
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()) //aflu caile de cost minim
	{
		c=q.front();
		d=c;
		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;
			}
		}
	}
	
	rez.x=n; rez.y=m;
	c.x=x2; c.y=y2;
	q.push(c);
	
	while(maxim<a[x2][y2]) //merg la jumatatile lor
	{
		c=q.front();
		d=c;
		q.pop();
		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);
		}
		maxim+=2;
	}
	
	rez=q.front();
	while(q.size()) //aflu unde se vor intalni
	{
		c=q.front();
		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;
			}
		}
		fscanf(f,"%c\n");
	}
	
	BFS();
	
	if(a[x2][y2]%2) fprintf(s,"%d ",a[x2][y2]/2+1);
	else fprintf(s,"%d ",a[x2][y2]/2);
	
	fprintf(s,"%d %d",rez.x,rez.y);
	
	fclose(f);
	
	return 0;
}