Cod sursa(job #1322967)

Utilizator BLz0rDospra Cristian BLz0r Data 20 ianuarie 2015 16:02:59
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define Nmax 101
#define inf 32500

FILE *f=fopen ("rj.in","r");
FILE *g=fopen ("rj.out","w");

struct point{
	int x, y;
}R, J, aux, auxx, poz;

char v[Nmax][Nmax];
short int cost[2][Nmax][Nmax];
const int d[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
queue < point > Q;
int N, M, sol=inf;

bool inside (int x, int y){
	if (x > 0 && y > 0 && x <= N && y <= M) return 1;
	return 0;
}

void LEE (point start, int ind){
	while (!Q.empty()) Q.pop();
	
	Q.push (start);
	cost[ind][start.x][start.y] = 0;
	
	while (!Q.empty()){
		aux = Q.front();
		Q.pop();
		for (int i = 0; i < 8; ++i){
			int xx=d[i][0]+aux.x, yy=d[i][1]+aux.y;
			if (v[xx][yy] == ' ' && cost[ind][xx][yy] > cost[ind][aux.x][aux.y]+1  && inside(xx,yy)){
				auxx.x = xx;
				auxx.y = yy;
				cost[ind][xx][yy] = cost[ind][aux.x][aux.y]+1;
				
				Q.push (auxx);
			}
		}
	}
}

int main(){
	
	fscanf (f,"%d%d%*c",&N,&M);
	
	for (int i = 1 ; i <= N; ++i){
		fgets (v[i]+1,105,f);
		if (R.x == 0){
			char *p = strchr (v[i]+1,'R');
			if (p != NULL){
				R.x = i;
				R.y = p - v[i];
			}
		}
		if (J.x == 0){
			char *p = strchr (v[i]+1,'J');
			if (p != NULL){
				J.x = i;
				J.y = p - v[i];
			}
		}
	}
	
	for (int k = 0; k <= 1; ++k)
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j)
				cost[k][i][j] = inf;
	
	LEE (R,0);
	LEE (J,1);
	
	
	for (int i = 1; i <= N ;++i){
		for (int j = 1 ; j <= M ; ++j){
			if (cost[0][i][j] == cost[1][i][j] && cost[0][i][j] < sol){
				sol = cost[0][i][j];
				poz.x = i;
				poz.y = j;
			}
		}
	}

	fprintf (g,"%d %d %d",sol+1, poz.x, poz.y); 
	
	return 0;
}