Cod sursa(job #2180151)

Utilizator flibiaVisanu Cristian flibia Data 20 martie 2018 17:43:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>
#define INF 123456789

using namespace std;

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

struct lol{
	int x, y;
};

const int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};

int n, m, x, y, bst = INF, d[2][110][110];
bool viz[2][110][110];
string s;
lol R, J;
queue <lol> q;

void bfs(lol P, int tip){
	q.push(P);
	d[tip][P.x][P.y] = 1;
	viz[tip][P.x][P.y] = 1;
	while(!q.empty()){
		lol p = q.front();
		q.pop();
		for(int k = 0; k < 8; k++){
			int px = p.x + dx[k];
			int py = p.y + dy[k];
			if(!viz[tip][px][py]){
				viz[tip][px][py] = 1;
				d[tip][px][py] = d[tip][p.x][p.y] + 1;
				q.push({px, py});
			} 
		}
	}
}

int main(){
	in >> n >> m;
	getline(in, s);
	for(int i = 1; i <= n; i++){
		getline(in, s);
		for(int j = 0; j < min((int)s.size(), m); j++){
			viz[0][i][j + 1] = viz[1][i][j + 1] = (s[j] == 'X');
			if(s[j] == 'R'){
				R.x = i;
				R.y = j + 1;
			}
			if(s[j] == 'J'){
				J.x = i;
				J.y = j + 1;
			}
		}
	}
	for(int i = 0; i <= n + 1; i++)
		viz[0][i][0] = viz[1][i][0] = viz[0][i][m + 1] = viz[1][i][m + 1] = 1;
	for(int j = 0; j <= m + 1; j++)
		viz[0][0][j] = viz[1][0][j] = viz[0][n + 1][j] = viz[1][n + 1][j] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			d[0][i][j] = d[1][i][j] = INF; 
	bfs(R, 0);
	bfs(J, 1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(d[0][i][j] == d[1][i][j] && d[0][i][j] < bst){
				bst = d[0][i][j];
				x = i;
				y = j;
			}
	out << bst << ' ' << x << ' ' << y;
	return 0;
}