Cod sursa(job #583539)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 20 aprilie 2011 18:50:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<stdio.h>
#define N 101
const int dx[8]={0,1,0,-1,1,-1,-1,1},dy[8]={1,0,-1,0,1,-1,1,-1};

struct punct {
	char lin,col;
};
int m,n,a[N][N],aa2[N][N];
short x1,y1,x2,y2;
char aa[N];

punct q[N*N];
int p=1,u;

void bfs(punct xx) {
	punct y; int i;
	q[++u]=xx;
	a[xx.lin][xx.col]=1;
	while(p<=u) {
		xx=q[p++];
		for(i=0;i<8;++i) {
			y.lin=xx.lin+dx[i];
			y.col=xx.col+dy[i];
			if(a[y.lin][y.col]==0) {
				q[++u]=y;
				a[y.lin][y.col]=1+a[xx.lin][xx.col];
			}
		}
	}
}

int main() {
	int i,j,smin=10000,a1,a2; punct w;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for(i=1;i<=n;++i) {
		gets(aa);
		for(j=0;j<m;++j) {
			if(aa[j]=='X')
				a[i][j+1]=-1;
			if(aa[j]=='R') {
				x1=i; y1=j+1;
			}
			if(aa[j]=='J') {
				x2=i;y2=j+1;
			}
		}
	}
	for(i=0;i<=n+1;++i) {
		a[i][0]=-1; a[i][m+1]=-1;
	}
	for(j=0;j<=m+1;++j) {
		a[0][j]=-1; a[n+1][j]=-1;
	}
	w.lin=x1; w.col=y1;
	bfs(w);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j) {
			aa2[i][j]=a[i][j];
			if(a[i][j]!=-1)
				a[i][j]=0;
		}
	w.lin=x2; w.col=y2;
	u=0; p=1;
	bfs(w);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j) {
			if(a[i][j]==aa2[i][j] && a[i][j]!=0 && a[i][j]!=-1 && a[i][j]<smin) {
				smin=a[i][j]; a1=i; a2=j;
			}
		}
	printf("%d %d %d",smin,a1,a2);
	return 0;
}