Cod sursa(job #2559143)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 27 februarie 2020 08:14:38
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <cstdio>
#include <queue>
#define pi std::pair<int,int>
#define x first
#define y second

const int inf = 1e9;
const int nmax = 105;

int d[3][nmax][nmax];
bool viz[nmax][nmax],precviz[nmax][nmax];
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 z, int n, int m){
	return (z.x > 0 and z.y > 0 and z.x <= n and z.y <= m);
}

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

int main()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	int n, m;
	pi romeo, julieta;
	char ch;
	scanf("%d%d\n", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%c", &ch);
			viz[i][j] = precviz[i][j] = (ch == 'X');
			if (ch == 'R')
				romeo = { i,j };
			if (ch == 'J')
				julieta = { i,j };
		}
		if(i!=n)
		scanf("\n");
	}
	bfs(romeo, n, m, 0);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			viz[i][j] = precviz[i][j];
	bfs(julieta, n, m, 1);
	pi ans = { -1,-1 };
	int mn = inf;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (d[0][i][j] == d[1][i][j] and d[0][i][j] and d[0][i][j] < mn)
					mn = d[0][i][j], ans = { i,j };
	printf("%d %d %d", mn, ans.x, ans.y);
}