Cod sursa(job #2729297)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 martie 2021 16:02:23
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <queue>
#define pi std::pair<int, int>
#define x first
#define y second

const int N = 105;

bool viz[2][N][N];
int n, m, dist[2][N][N];
int dx[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

bool isin(pi a) { return (1<=a.x and a.x<=n and 1<=a.y and a.y<=m); }

void bfs(pi source, int k) {
	std::queue<pi>q;
	viz[k][source.x][source.y] = 1;
	q.push(source);
	while(!q.empty()) {
		pi curr = q.front();
		q.pop();
		for(int i=0;i<8;i++) {
			pi vec = {curr.x+dx[i], curr.y+dy[i]};
			if(isin(vec) and !viz[k][vec.x][vec.y]) {
				q.push(vec);
				viz[k][vec.x][vec.y] = 1;
				dist[k][vec.x][vec.y] = dist[k][curr.x][curr.y] + 1;
			}
		}
	}
}

int main() {
	std::ifstream fin("rj.in");
	std::ofstream fout("rj.out");
	pi source, sink;
	char ch;
	fin>>n>>m;
	fin.ignore(1);
	for(int i=1;i<=n;i++){
		char c[N];
		fin.getline(c, N);
		for(int j=1;j<=m;j++){
			ch = c[j-1];
			if(j!=m+1) {
				if(ch=='X') viz[0][i][j] = viz[1][i][j] = 1;
				if(ch=='R') source = {i, j};
				if(ch=='J') sink = {i, j};
			}
		}
	}
	bfs(source, 0);
	bfs(sink, 1);
	int mn = 100000000, ansx, ansy;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(dist[0][i][j] == dist[1][i][j] and dist[0][i][j] and mn>dist[0][i][j]) mn = dist[0][i][j], ansx = i, ansy = j;
	fout<<mn + 1<<" "<<ansx<<" "<<ansy;
}