Cod sursa(job #542173)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 25 februarie 2011 21:30:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <queue>
#include <utility>

//EIUCLAP

using namespace std;

//consts
const int NMAX=128;
const int VXY=8;
const int vx[VXY]={0,0,1,-1,1,-1,1,-1},vy[VXY]={1,-1,0,0,-1,1,1,-1};

//structs
typedef char Matrix[NMAX][NMAX];

//functions
/*inline void print_matrix(Matrix v, int n, int m){
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j)
			printf("%d ",v[i][j]);
		printf("\n");
	}
	printf("\n");
}*/

void lee_function(Matrix v, int startx, int starty, int n, int m){
	//vars
	int i;//cycle
	int x,y,xx,yy;//circulary
	queue<pair<int,int> > leeq;
	v[startx][starty]=1;
	leeq.push(make_pair(startx,starty));
	
	//body
	while(!leeq.empty()){
		x=leeq.front().first;
		y=leeq.front().second;
		leeq.pop();
		for(i=0;i<VXY;++i)
		{
			xx=x+vx[i];
			yy=y+vy[i];
			if(xx<n && yy<m && xx>=0 && yy>=0 && !v[xx][yy]){
				v[xx][yy]=v[x][y]+1;
				leeq.push(make_pair(xx,yy));
			}
		}
	}
	
	return;
}

int main(){
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	//vars
	int n,m;//input
	Matrix romeo,juliet;
	int rx,ry,jx,jy;//start positions
	int i,j;//cycle
	
	//read
	char x;
	scanf("%d%d\n",&n,&m);
	for(i=0;i<n;++i){
		for(j=0;j<m;++j){
			scanf("%c",&x);
			switch(x){
				case 'X':
					romeo[i][j]=juliet[i][j]=-1;
					break;
				case 'R':
					rx=i;
					ry=j;
					break;
				case 'J':
					jx=i;
					jy=j;
					break;
			}
		}
		scanf("\n\r");
	}
	
	
	//body
	lee_function(romeo,rx,ry,n,m);
	lee_function(juliet,jx,jy,n,m);
	
	//solution
	int sol=NMAX,solx,soly;
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			if(romeo[i][j]!=-1 && romeo[i][j]==juliet[i][j] && romeo[i][j]<sol){
				sol=romeo[i][j];
				solx=i;
				soly=j;
			}
	printf("%d %d %d\n",sol,solx+1,soly+1);
	
	return 0;
}