Cod sursa(job #2729293)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 martie 2021 15:55:47
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <queue>
#define pi std::pair<int, int>
#define x first
#define y second

const int N = 105;

bool viz[3][N][N];
int n, m, dist[2][N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -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<4;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() {
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	pi source, sink;
	char ch;
	scanf("%d %d\n", &n, &m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m+1;j++){
			scanf("%c", &ch);
			if(j!=m+1) {
				if(ch=='X') viz[0][i][j] = viz[1][i][j] = viz[2][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;
	printf("%d %d %d", mn, ansx, ansy);
}