Cod sursa(job #151446)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 8 martie 2008 10:44:42
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#define max 150
char a[max][max],c;
int ans[2][max][max],st[max*max],n,m;
int p,p1;
const int d1[10]={0,-1,-1,-1,0,1,1,1,0};
const int d2[10]={0,-1,0,1,1,1,0,-1,-1};
int main(){
	int i,j,nr=1,x,y,pi,pj,min=10000;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;++i){
		fgets(a[i],max,stdin);
		for(j=0;j<m;++j)
			if(a[i][j]=='\n')break;
		for(;j<m;++j)a[i][j]=' ';
	}
	for(i=1;i<=n;++i){
		for(j=0;j<m;++j){
			ans[0][i][j]=-1;
			ans[1][i][j]=-1;
		}
	}
	c='R';
	for(;nr>=0;--nr){
		for(i=1;i<=n;++i)
			for(j=0;j<m;++j){
				if(a[i][j]==c){
					p=i;
					p1=j;
				}
			}
		st[0]=0;
		st[++st[0]]=p*101+p1;
		ans[nr][p][p1]=0;
		for(i=1;i<=st[0];++i){
			x=st[i]/101;
			y=st[i]%101;
			for(j=1;j<=8;++j){
				if(x+d1[j]<=0||x+d1[j]>n||y+d2[j]<0||y+d2[j]>=m)
					continue;
				if(a[x+d1[j]][y+d2[j]]==' '&&ans[nr][x+d1[j]][y+d2[j]]==-1){
					st[++st[0]]=(x+d1[j])*101+(y+d2[j]);
					ans[nr][x+d1[j]][y+d2[j]]=ans[nr][x][y]+1;
				}
			}
		}
		c='J';
	}
	for(i=1;i<=n;++i)
		for(j=0;j<m;++j){
			if(min>ans[0][i][j]&&ans[0][i][j]!=-1&&ans[1][i][j]==ans[0][i][j]){
				min=ans[0][i][j];
				pi=i;
				pj=j+1;
			}
		}
	printf("%d %d %d",min+1,pi,pj);
	printf("\n");
	return 0;
}