Cod sursa(job #757024)

Utilizator ephgstefana gal ephg Data 10 iunie 2012 21:30:52
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define BM 105
using namespace std;
typedef pair <int,int> per;
queue <per> c;
per ro,jul;
int r[BM][BM],ju[BM][BM], dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,1,-1,1,0,-1},n,m;
bool check(int i,int j){
	if(i<1||j<1||i>n||j>m)return 0;
	return 1;
}
void frumos (int a[BM][BM],per b){
	int d;
	for(c.push(b);c.size();c.pop()){
		per fr=c.front();
		for(d=0;d<8;++d){
			int ii=fr.first+dx[d],jj=fr.second+dy[d];
			if(check(ii,jj)&&a[ii][jj]==0&&(ii!=b.first||jj!=b.second)){
				a[ii][jj]=a[fr.first][fr.second]+1;
				c.push(make_pair(ii,jj));
			}
		}
	}
}
int main (){
	int i,j,mini,minj,drmin=9999;
	char cc;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;++i){
		scanf("\n");
		for(j=1;j<=m;++j){
			scanf("%c",&cc);
			if(cc=='X'){
				r[i][j]=-1;
				ju[i][j]=-1;
			}
			if(cc=='R'){
				ro.first=i;
				ro.second=j;
			}
			if(cc=='J'){
				jul.first=i;
				jul.second=j;
			}
		}
	}
	frumos(r,ro);
	frumos(ju,jul);
	/*for(i=1;i<=n;++i){
		for(j=1;j<=m;++j)fprintf(stderr,"%d ",r[i][j]);
		fprintf(stderr,"\n");
	}
	fprintf(stderr,"\n");
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j)fprintf(stderr,"%d ",ju[i][j]);
		fprintf(stderr,"\n");
	}*/
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(r[i][j]<ju[i][j])r[i][j]=ju[i][j];
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(drmin>r[i][j]&&r[i][j]!=-1&&r[i][j]!=0){
		drmin=r[i][j];
		mini=i;
		minj=j;
	}
	printf("%d %d %d",drmin+1,mini,minj);
	return 0;
}