Cod sursa(job #705408)

Utilizator swim406Teudan Adina swim406 Data 4 martie 2012 11:09:40
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<fstream>
#include<string>
using namespace std;
char ch;
struct coada {
	int x,y;
};
coada c[10202];
int m,n;
int romeo[101][101],rsx,rsy;
int julieta[101][101],jsx,jsy;
void lee(int v[][101], int a, int b) {
	int cs=1, ci=1;
	c[ci].x=a;
	c[ci].y=b;
	while(ci<=cs) {
		if(v[c[ci].x-1][c[ci].y]==0) {
			v[c[ci].x-1][c[ci].y]=v[c[ci].x][c[ci].y]+1;
			cs++;
			c[cs].x=c[ci].x-1;
			c[cs].y=c[ci].y;
		}
		if(v[c[ci].x+1][c[ci].y]==0) {
			v[c[ci].x+1][c[ci].y]=v[c[ci].x][c[ci].y]+1;
			cs++;
			c[cs].x=c[ci].x+1;
			c[cs].y=c[ci].y;
		}
		if(v[c[ci].x][c[ci].y-1]==0) {
			v[c[ci].x][c[ci].y-1]=v[c[ci].x][c[ci].y]+1;
			cs++;
			c[cs].x=c[ci].x;
			c[cs].y=c[ci].y-1;
		}
		if(v[c[ci].x][c[ci].y+1]==0) {
			v[c[ci].x][c[ci].y+1]=v[c[ci].x][c[ci].y]+1;
			cs++;
			c[cs].x=c[ci].x;
			c[cs].y=c[ci].y+1;
		}
		ci++;
	}
	for(int i=1;i<=m;i++) 
		for(int j=1;j<=n;j++) 
			if(v[i][j]==0) v[i][j]=-1;
	v[a][b]=0;
}
int main() {
	ifstream f("rj.in"); 
	ofstream g("rj.out");
	int i,j;
	f>>m>>n;
	for(i=1;i<=m;i++) {
		if(f.peek()=='\n') f.get();
		for(j=1;j<=n;j++) { ch=f.get();
			if(ch==' ') {
				romeo[i][j]=0;
				julieta[i][j]=0;
			}
			if(ch=='R') {
				rsx=i;
				rsy=j;
				julieta[i][j]=0;
				romeo[i][j]=0;
			}
			if(ch=='J') {
				jsx=i;
				jsy=j;
				julieta[i][j]=0;
				romeo[i][j]=0;
			}
			if(ch=='X') {
				julieta[i][j]=-1;
				romeo[i][j]=-1;
			}
		}
	}
	for(i=0;i<=m+1;i++) {
		julieta[i][0]=-1;
		julieta[i][n+1]=-1;
		romeo[i][0]=-1;
		romeo[i][n+1]=-1;
	}
	for(i=0;i<=n+1;i++) {
		julieta[0][i]=-1;
		julieta[m+1][i]=-1;
		romeo[0][i]=-1;
		romeo[m+1][i]=-1;
	}
	int min=m*n,a,b;
	lee(romeo,rsx,rsy);
	lee(julieta,jsx,jsy);
	for(i=m;i>=1;i--) 
		for(j=n;j>=1;j--)
			if(romeo[i][j]==julieta[i][j] && romeo[i][j]!=-1 && romeo[i][j]<=min) {
				min=romeo[i][j];
				a=i;
				b=j;
			}
	g<<min<<" "<<a<<" "<<b;
	return 0;
}