Cod sursa(job #757255)

Utilizator davidoceaSintamarian David davidocea Data 11 iunie 2012 16:41:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define BN 105
using namespace std;
typedef pair<short,short> per;
queue <per> c;
int dx[]={-1,-1,-1,1,1,1,0,0},n,m;
int dy[]={0,1,-1,0,1,1,-1,1};
short r[BN][BN];
short ju[BN][BN];
char ma[BN][BN];
per rp,jp,a;
per sol;
int check(int i,int j){
	if(i<1||j<1||i>n||j>m) return 0;
	return 1;
}
void start(short mat[BN][BN],per a){
	int d;
	for(c.push(a);c.size();c.pop()){
		per fr=c.front();
		for(d=0;d<8;++d){
			int i=fr.first+dx[d];int j=fr.second+dy[d];
			if(check(i,j)&&mat[i][j]==-1){
				mat[i][j]=mat[fr.first][fr.second]+1;
				c.push(make_pair(i,j));
			}
		}
	}
}

int main(){
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	int i,j,min=89589753;
	for(i=1;i<=n;++i){
		fgets(ma[i]+1,105,stdin);
	}
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			if(ma[i][j]=='X'){
				r[i][j]=ju[i][j]=-2;
			}
			else if(ma[i][j]==' '){
				r[i][j]=ju[i][j]=-1;
			}
			else if(ma[i][j]=='R'){
				r[i][j]=1;ju[i][j]=-1;
				rp=make_pair(i,j);
			}
			else {
				r[i][j]=-1;ju[i][j]=1;
				jp=make_pair(i,j);
			}
		}
	}
	start(r,rp);
	start(ju,jp);
	for(i=1;i<=n;++i){
		for(j=1;j<=n;++j){
			ma[i][j]=-20;
			if(r[i][j]==ju[i][j]&&min>r[i][j]&&r[i][j]>0){
				min=r[i][j];
				sol.first=i;
				sol.second=j;
			}
		}
	}
	printf("%d %d %d",min,sol.first,sol.second);
	return 0;
}