Cod sursa(job #704698)

Utilizator RobertBBadea Corneliu Robert RobertB Data 2 martie 2012 19:44:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

short oras[101][101];
short a[101][101],b[101][101];
int xj,yr,yj,xr;
int N,M;
int Min = 100000,Mini,Minj;

struct q {
	int x;
	int y;
};

queue <q> coada;

ifstream f("rj.in");
ofstream g("rj.out");

int inside_the_matrix(int x, int y)
{
	return x >= 1 || y >= 1 || x <= N || y <= M || oras[x][y] != 'X';
}

void BFS(int x, int y, short mat[][101]) {
	q aux;
	aux.x = x;
	aux.y = y;
	mat[x][y] = 1;
	coada.push(aux);
	while(!coada.empty()) {
		x = coada.front().x;
		y = coada.front().y;
		coada.pop();
		if(inside_the_matrix(x - 1, y) && mat[x][y] + 1 < mat[x-1][y]) {
			mat[x-1][y] = mat[x][y] + 1;
			aux.x = x-1;
			aux.y = y;
			coada.push(aux);
		}
		if(inside_the_matrix(x + 1, y) && mat[x][y] + 1 < mat[x+1][y]) {
			mat[x+1][y] = mat[x][y] + 1;
			aux.x = x+1;
			aux.y = y;
			coada.push(aux);
		}
		if(inside_the_matrix(x, y - 1) && mat[x][y] + 1 < mat[x][y-1]) {
			mat[x][y-1] = mat[x][y] + 1;
			aux.x = x;
			aux.y = y-1;
			coada.push(aux);
		}
		if(inside_the_matrix(x, y + 1) && mat[x][y] + 1 < mat[x][y+1]) {
			mat[x][y+1] = mat[x][y] + 1;
			aux.x = x;
			aux.y = y+1;
			coada.push(aux);
		}
		if(inside_the_matrix(x - 1, y - 1) && mat[x][y] + 1 < mat[x-1][y-1]) {
			mat[x-1][y-1] = mat[x][y] + 1;
			aux.x = x-1;
			aux.y = y-1;
			coada.push(aux);
		}
		if(inside_the_matrix(x - 1, y + 1) && mat[x][y] + 1 < mat[x-1][y+1]) {
			mat[x-1][y+1] = mat[x][y] + 1;
			aux.x = x-1;
			aux.y = y+1;
			coada.push(aux);
		}
		if(inside_the_matrix(x + 1, y - 1) && mat[x][y] + 1 < mat[x+1][y-1]) {
			mat[x+1][y-1] = mat[x][y] + 1;
			aux.x = x+1;
			aux.y = y-1;
			coada.push(aux);
		}
		if(inside_the_matrix(x + 1, y + 1) && mat[x][y] + 1 < mat[x+1][y+1]) {
			mat[x+1][y+1] = mat[x][y] + 1;
			aux.x = x+1;
			aux.y = y+1;
			coada.push(aux);
		}
	}
}

void find() 
{
	int i,j;
	for(i = 1; i <= N; i++) {
		for(j = 1; j <= M ; j++) {
			if(a[i][j] == b[i][j] && a[i][j] != 10000 && a[i][j] != 0 && a[i][j] != -1) {
				if(a[i][j] < Min) {
					Min = a[i][j];
					Mini = i;
					Minj = j;
				}
			}
		}
	}
}

int main()
{
	char sir[100];
	int i,j;
	f>>N>>M;
	f.get();
	for(i = 1; i <= N; i++) {
		f.getline(sir,M+1);
		for(j = 0 ; j < M ; j++) {
			if(sir[j] == ' ') {
				oras[i][j+1] = 0;
				a[i][j+1] = 10000;
				b[i][j+1] = 10000;
			} else if(sir[j] == 'X') {
				oras[i][j+1] = 1;
				a[i][j+1] = -1;
				b[i][j+1] = -1;
			} else if(sir[j] == 'R') {
				oras[i][j+1] = 2;
				xr = i;
				yr = j+1;
			} else if(sir[j] == 'J') {
				oras[i][j+1] = 3;
				xj = i;
				yj = j+1;
			}
		}
	}
	BFS(xr,yr,a);
	BFS(xj,yj,b);
	find();
	g<<Min<<" "<<Mini<<" "<<Minj;
}