Cod sursa(job #501138)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 14 noiembrie 2010 14:03:31
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<fstream.h>
#include<limits.h>
typedef struct{int x1,y1,x2,y2,r,j;}COADA;
typedef struct{char r1,j1;}VECTOR;
int N,M,n,m,c,d;
VECTOR v[101][101];
int interior(int m,int n){if(m>=1 && m<=N && n>=1 && n<=M) return 1;else return 0;}
int blocaj(int c,int d){if(!(v[c][d-1].r1=='X' && v[c-1][d].r1=='X') || !(v[c+1][d].r1=='X' && v[c][d-1].r1=='X') || !(v[c+1][d].r1=='X' && v[c][d+1].r1=='X') || !(v[c][d+1].r1=='X' && v[c-1][d].r1=='X') || !(v[c][d-1].j1=='X' && v[c-1][d].j1=='X') || !(v[c+1][d].j1=='X' && v[c][d-1].j1=='X') || !(v[c+1][d].j1=='X' && v[c][d+1].j1=='X') || !(v[c][d+1].j1=='X' && v[c-1][d].j1=='X')) return -1;else return 0;}
int main ()
{
	COADA C[9801],a,b;
	ifstream f("rj.in");
	ofstream g("rj.out");
	int x,y,p,u1,u2,i,j,xn,yn,ok,tmin,x1,y1,x2,y2,min=INT_MAX;
	char 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;
	f.get(c);
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++){
			f.get(c);v[i][j].r1=v[i][j].j1=c;
			if(v[i][j].r1=='R') {a.r=i;b.r=j;v[i][j].r1=' ';} //indici romeo
			else if(v[i][j].j1=='J') {a.j=i;b.j=j;v[i][j].j1=' ';} //indici julieta
		}
		f.get(c);
	}
	p=u1=1;C[u1].x1=a.r;C[u1].y1=b.r;v[a.r][b.r].r1='1';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 && blocaj(xn,yn)==-1 && (v[xn][yn].r1==' '|| v[xn][yn].r1=='J')){
				if(xn==a.j && yn==b.j) {ok=1;break;}
				v[xn][yn].r1=v[x1][y1].r1+1;
				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].j1='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 && blocaj(xn,yn)==-1 && (v[xn][yn].j1==' ' || v[xn][yn].j1=='R')){
				if(xn==a.r && yn==b.r){ok=1;break;}
				v[xn][yn].j1=v[x2][y2].j1+1;
				C[++u2].x2=xn;C[u2].y2=yn; //introduc coordonatele julietei in coada
			}
		}
		p++;
	}
	for(i=1;i<=u1;i++){
		for(j=1;j<=u2;j++){
			if(C[i].x1==C[j].x2 && C[i].y1==C[j].y2 && v[C[i].x1][C[i].y1].r1==v[C[j].x2][C[j].y2].j1 && (v[C[i].x1][C[i].y1].r1-'0')<min) {min=v[C[i].x1][C[i].y1].r1-'0';x=C[i].x1;y=C[i].y1;}
		}
	}
	tmin=min;
	g<<tmin<<" "<<x<<" "<<y;
	f.close();
	g.close();
	return 0;
}