Cod sursa(job #122705)

Utilizator swift90Ionut Bogdanescu swift90 Data 13 ianuarie 2008 15:35:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
const int dl[]={-1,-1,0,1,1,1,0,-1};
const int dc[]={0,1,1,1,0,-1,-1,-1};
struct cod{
	int x,y;
};
cod coada[21000],cost[105][105];
int nr[105][105],apar[105][105];
char linie[110];
inline int max(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	int n,m,i,j,x1,x2,y1,y2,p,u,x,y,tmin=100000000;
	scanf("%d%d",&n,&m);
	fgets(linie,110,stdin);
	for(i=1;i<=n;++i){
		fgets(linie,110,stdin);
		for(j=0;j<m;++j){
			if(linie[j]=='X')
				nr[i][j+1]=1;
			if(linie[j]=='R'){
				x1=i;
				y1=j+1;
				apar[x1][y1]=1;
			}
			if(linie[j]=='J'){
				x2=i;
				y2=j+1;
			}
		}
	}
	for(i=0;i<=m+1;++i)
		nr[0][i]=nr[n+1][i]=1;
	for(i=0;i<=n+1;++i)
		nr[i][0]=nr[i][m+1]=1;
	coada[0].x=x1;
	coada[0].y=y1;
	p=0;
	u=1;
	cost[x1][y1].x=1;
	while(p!=u){
		for(i=0;i<8;++i){
			if(nr[coada[p].x+dl[i]][coada[p].y+dc[i]]==0 && apar[coada[p].x+dl[i]][coada[p].y+dc[i]]==0){
				coada[u].x=coada[p].x+dl[i];
				coada[u].y=coada[p].y+dc[i];
				cost[coada[u].x][coada[u].y].x=cost[coada[p].x][coada[p].y].x+1;
				apar[coada[u].x][coada[u].y]=1;
				++u;
			}
		}
		++p;
	}
	coada[0].x=x2;
	coada[0].y=y2;
	p=0;
	u=1;
	cost[x2][y2].y=1;
	while(p!=u){
		for(i=0;i<8;++i){
			if(nr[coada[p].x+dl[i]][coada[p].y+dc[i]]==0 && apar[coada[p].x+dl[i]][coada[p].y+dc[i]]!=2){
				coada[u].x=coada[p].x+dl[i];
				coada[u].y=coada[p].y+dc[i];
				cost[coada[u].x][coada[u].y].y=cost[coada[p].x][coada[p].y].y+1;
				apar[coada[u].x][coada[u].y]=2;
				++u;
			}
		}
		++p;
	}
	
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			if(nr[i][j]==0){
				if((i!=x1 && j!=y1) || (i!=x2 && j!=y2)){
					if(cost[i][j].x>0 || cost[i][j].y>0){
						if(tmin>max(cost[i][j].x,cost[i][j].y)){
							tmin=max(cost[i][j].x,cost[i][j].y);
							x=i;
							y=j;
						}
					}
				}
			}
		}
	}
	
	
	printf("%d %d %d\n",tmin,x,y);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}