Cod sursa(job #189691)

Utilizator fogabFodor Gabor fogab Data 17 mai 2008 06:00:25
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#define N 105 
struct ceva
{int x,y;};
ceva coada[10505];
char s[2*N];
int b[N][N],c[N][N],n,m;
int xr,yr,xj,yj,min,ok=1,x,y;
bool a[N][N];
const int dx[]={-1,1,0,1, 0,-1,-1, 1};
const int dy[]={-1,1,1,0,-1, 0, 1,-1};

void scan()
{
	freopen("rj.in", "r",stdin);
	freopen("rj.out", "w",stdout);
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<=n;gets(s+1),++i)
		for(int j=1;j<=m;j++)
		switch(s[j])
		{
			case 'R':
			{
				xr=i;
				yr=j;
				b[xr][yr]=1;
				break;
			}
			case 'J':
			{
				xj=i;
				yj=j;
				c[xj][yj]=1;
				break;
			}
			case 'X':
				a[i][j]=1;
		}	
}		
void bfs(int x,int y,int d[N][N])
{
	int u=1;
	coada[1].x=x;
	coada[1].y=y;
	for(int i=1;i<=u;++i)
		for(int j=0;j<8;++j)
			if (coada[i].x+dx[j]>0 && coada[i].x+dx[j]<=n && coada[i].y+dy[j]>0 && coada[i].y+dy[j]<=m && !d[coada[i].x+dx[j]][coada[i].y+dy[j]] && !a[coada[i].x+dx[j]][coada[i].y+dy[j]])  
            {  
                d[coada[i].x+dx[j]][coada[i].y+dy[j]]=d[coada[i].x][coada[i].y]+1;  
                coada[++u].x=coada[i].x+dx[j];  
                coada[u].y=coada[i].y+dy[j];  
            }
	
}
void solve()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if (b[i][j]==c[i][j] && b[i][j] && (b[i][j]<min || ok))
			{
				min=b[i][j];
				x=i;
				y=j;
				ok=0;
			}
	printf("%d %d %d\n",min,x,y);
}	
int main()
{
	scan();
	bfs(xr,yr,b);
	bfs(xj,yj,c);
	solve();
	return 0;
}