Cod sursa(job #500768)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 13 noiembrie 2010 00:08:55
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<fstream.h>
#include<limits.h>
typedef struct{int x1,y1,x2,y2,r,j;}COADA;
int N,M,n,m;
int interior(int m,int n){if(m>=1 && m<=N && n>=1 && n<=M) return 1;else return 0;}
int main ()
{
	ifstream f("rj.in");
	ofstream g("rj.out");
	COADA C[9801],a,b,nr;
	int x,y,p,u1,u2,i,j,xn,yn,ok,tmin,x1,y1,x2,y2,min=INT_MAX;
	char v[101][101],c;
	int dx[]={0,-1,0,1,0,-1,1,1,-1};
	int dy[]={0,0,1,0,-1,1,1,-1,-1};
	f>>N>>M;
	c=f.get();
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++){
			c=f.get();v[i][j]=c;
			if(v[i][j]=='R') {a.r=i;b.r=j;} //indici romeo
			else if(v[i][j]=='J') {a.j=i;b.j=j;} //indici julieta
		}
		c=f.get();
	}
	p=u1=1;C[u1].x1=a.r;C[u1].y1=b.r;ok=0; //coordonate romeo 1 si 1
	while(p<=u1 && ok==0){
		x1=C[p].x1;y1=C[p].y1;
		for(i=1;i<=8;i++){
			xn=x1+dx[i];
			yn=y1+dy[i];
			if(interior(xn,yn)==1 && v[xn][yn]==' '|| v[xn][yn]=='J'){
				if(xn==a.j && yn==b.j) {ok=1;nr.r=(v[x1][y1]-'0')+1;break;}
				v[xn][yn]='0';
				C[++u1].x1=xn;C[u1].y1=yn; //introduc coordonatele lui romeo in coada
			}
		}
		p++;
	}
	p=u2=1;C[u2].x2=a.j;C[u2].y2=b.j;v[a.j][b.j]='1';ok=0; //coordonate julieta 5 si 3
	while(p<=u2 && ok==0){
		x2=C[p].x2;y2=C[p].y2;
		for(i=1;i<=8;i++){
			xn=x2+dx[i];
			yn=y2+dy[i];
			if(interior(xn,yn)==1 && v[xn][yn]=='0' || v[xn][yn]=='R'){
				if(xn==a.r && yn==b.r){ok=1;break;}
				v[xn][yn]=v[x2][y2]+1;
				C[++u2].x2=xn;C[u2].y2=yn; //introduc coordonatele julietei in coada
			}
		}
		p++;
	}
	ok=0;
	for(i=1;i<=u1 && ok==0;i++){
		for(j=1;j<=u2 && ok==0;j++){
			if(C[i].x1==C[j].x2 && C[i].y1==C[j].y2 && (v[C[i].x1][C[i].y1]-'0')<min && i-j==0) {min=v[C[i].x1][C[i].y1]-'0';x=C[i].x1;y=C[i].y1;ok=1;}
		}
	}
	tmin=min;
	g<<tmin<<" "<<x<<" "<<y;
	f.close();
	g.close();
	return 0;
}