Cod sursa(job #2695154)

Utilizator vladdudauDudau Vlad vladdudau Data 11 ianuarie 2021 22:41:51
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#define Val 123456789

using namespace std;

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

struct punct{
	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, mini = Val, distanta[2][101][101];
bool viz[2][101][101];
string s;
punct R, J;
queue <punct> q;

void bfs(punct P, int tip)
{
	q.push(P);
	distanta[tip][P.x][P.y] = 1;
	viz[tip][P.x][P.y] = 1;
	while(!q.empty()){
		punct 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;
				distanta[tip][px][py] = distanta[tip][p.x][p.y] + 1;
				q.push({px, py});
			}
		}
	}
}

int main(){
	fin >> n >> m;
	getline(fin, s);
	for(int i = 1; i <= n; i++){
		getline(fin, 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++)
			distanta[0][i][j] = distanta[1][i][j] = Val;
	bfs(R, 0);
	bfs(J, 1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(distanta[0][i][j] == distanta[1][i][j] && distanta[0][i][j] < mini){
				mini = distanta[0][i][j];
				x = i;
				y = j;
			}
	fout << mini << ' ' << x << ' ' << y;
	return 0;
}