Cod sursa(job #674851)

Utilizator razielreaperMatei Andrei razielreaper Data 6 februarie 2012 20:19:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>
#include<string.h>
#define inf 20000
const int dx[]={-1,-1,0,+1,+1,+1,0,-1};
const int dy[]={0,+1,+1,+1,0,-1,-1,-1};
typedef struct{int x;int y;}coada;
coada c[10000];
int a[102][102],b[102][102],i,j,st,dr,min,xmin,ymin,m,n,xr,yr,xj,yj;
char s;
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(i=0;i<=n+1;i++){a[i][0]=-1;a[i][m+1]=-1;b[i][0]=-1;b[i][m+1]=-1;}
	for(i=0;i<=m+1;i++){a[0][i]=-1;a[n+1][i]=-1;b[0][i]=-1;b[n+1][i]=-1;}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
		{scanf("%c",&s);if(s=='R'){xr=i;yr=j;a[i][j]=0;b[i][j]=inf;}
		                if(s=='J'){xj=i;yj=j;b[i][j]=0;a[i][j]=inf;}
						if(s=='X'){a[i][j]=-1;b[i][j]=-1;}
						if(s==' '){a[i][j]=inf;b[i][j]=inf;}
		}
		scanf("%c",&s);
	}
	st=1;dr=1;c[st].x=xr;c[st].y=yr;a[xr][yr]=1;
	while(st<=dr){
		for(i=0;i<=7;i++)
			if(a[c[st].x+dx[i]][c[st].y+dy[i]]==inf){
			a[c[st].x+dx[i]][c[st].y+dy[i]]=a[c[st].x][c[st].y]+1;
			dr++;
			c[dr].x=c[st].x+dx[i];c[dr].y=c[st].y+dy[i];
			}
		st++;
	}
		st=1;dr=1;c[st].x=xj;c[st].y=yj;b[xj][yj]=1;
	while(st<=dr){
		for(i=0;i<=7;i++)
			if(b[c[st].x+dx[i]][c[st].y+dy[i]]==inf){
			b[c[st].x+dx[i]][c[st].y+dy[i]]=b[c[st].x][c[st].y]+1;
			dr++;
			c[dr].x=c[st].x+dx[i];c[dr].y=c[st].y+dy[i];
			}
		st++;
	}
	min=10000;
	xmin=0;ymin=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==b[i][j]&&a[i][j]!=-1)
				if(a[i][j]<min){min=a[i][j];xmin=i;ymin=j;}
	printf("%d %d %d\n",a[xmin][ymin],xmin,ymin);
    return 0;
}