Cod sursa(job #412925)

Utilizator alexandrul_21Niculescu Mihai alexandrul_21 Data 7 martie 2010 00:24:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream.h>
int di[8]={-1,-1,0,1,1,1,0,-1},dj[8]={0,1,1,1,0,-1,-1,-1};
int m,n,i,j,ln,cn,lr,lj,cr,cj,l,d,c,b[100][100],e[100][100],x[10000],y[10000],p,u,k;
char a[100][100];
void cit(){
	int i,j;
	ifstream fin("rj.in");
	fin>>m>>n;
	fin.get();
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			a[i][j]=fin.get();
			if(a[i][j]=='R'){
				lr=i;
				cr=j;
			}
			if(a[i][j]=='J'){
				lj=i;
				cj=j;
			}
		}	
		fin.get();
	}
	fin.close();
}
int main(){
	cit();
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			b[i][j]=-1;
			e[i][j]=-1;
		}
	p=1;u=1;
	x[u]=lr;y[u]=cr;
	b[lr][cr]=1;
	while(p<=u){
		i=x[p];j=y[p];
		for(k=0;k<=7;k++){
			ln=i+di[k];cn=j+dj[k];
			if(ln>0&&ln<m+1&&cn>0&&cn<n+1&&a[ln][cn]==' '&&b[ln][cn]==-1){
				b[ln][cn]=b[i][j]+1;
				u++;
				x[u]=ln;
				y[u]=cn;
			}
		}
		p++;
	}
	p=1;u=1;
	x[u]=lj;y[u]=cj;
	e[lj][cj]=1;
	while(p<=u){
		i=x[p];j=y[p];
		for(k=0;k<=7;k++){
			ln=i+di[k];cn=j+dj[k];
			if(ln>0&&ln<m+1&&cn>0&&cn<n+1&&a[ln][cn]==' '&&e[ln][cn]==-1){
				e[ln][cn]=e[i][j]+1;
				u++;
				x[u]=ln;
				y[u]=cn;
			}
		}
		p++;
	}
	d=32000;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(b[i][j]==e[i][j]&&b[i][j]!=-1&&d>b[i][j]){
				d=b[i][j];
				l=i;
				c=j;
			}
	ofstream fout("rj.out");
	fout<<d<<" "<<l<<" "<<c;
	fout.close();
	return 0;
}