Cod sursa(job #431636)

Utilizator nandoLicker Nandor nando Data 1 aprilie 2010 11:23:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <cstring>

#define MAX 105
#define INF 0x3f3f3f3f
bool mat[MAX][MAX];
int p[2][MAX][MAX],list[MAX*MAX][3],lb,le,n,m,rx,ry,jx,jy;
char buf[MAX];
int dir[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}};

FILE* fin=fopen("rj.in","r");
FILE* fout=fopen("rj.out","w");

void lee(int idx,int sx,int sy){
	lb=le=0;
	list[0][0]=sx;
	list[0][1]=sy;
	list[0][2]=1;
	p[idx][sx][sy]=1;
	
	while(lb<=le){
		for(int i=0;i<8;i++){
			int dx=list[lb][0]+dir[i][0];
			int dy=list[lb][1]+dir[i][1];
			
			if(dx>=0&&dy>=0&&dx<n&&dy<m){
				if(mat[dx][dy]&&p[idx][dx][dy]==INF){
					p[idx][dx][dy]=list[lb][2]+1;
					le++;
					list[le][0]=dx;
					list[le][1]=dy;
					list[le][2]=list[lb][2]+1;
				}
			}
		}
		lb++;
	}
}

int main(){
	fscanf(fin,"%d %d\n",&n,&m);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			mat[i][j]=1;
			p[0][i][j]=p[1][i][j]=INF;
		}
	}
		
	for(int i=0;i<n;i++){
		fgets(buf,MAX,fin);
		for(int j=0;j<m;j++){
			if(buf[j]=='R'){
				rx=i,ry=j;
			}else if(buf[j]=='J'){
				jx=i,jy=j;
			}else if(buf[j]=='X'){
				mat[i][j]=false;
			}
		}
	}
	
	lee(0,rx,ry);
	lee(1,jx,jy);
		
	int mx,my,v=INF;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(p[0][i][j]==p[1][i][j]){
				if(p[0][i][j]<v){
					mx=i,my=j,v=p[0][i][j];
				}
			}
		}
	}
	fprintf(fout,"%d %d %d\n",v,mx+1,my+1);
	fclose(fin);
	fclose(fout);
	return 0;
}