Cod sursa(job #2422741)

Utilizator SemetgTemes George Semetg Data 19 mai 2019 20:22:31
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
using namespace std;

ifstream in{ "rj.in" };
ofstream out{ "rj.out" };

using Pair = pair<int, int>;

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

int n, m;
int a[105][105];
int dr[105][105], dj[105][105];
Pair R, J;

void citeste() {
	in >> n >> m;
	in.get();

	for (int i{ 0 }; i < n; ++i) {
		char s[105];
		in.getline(s, 105);

		for (int j{ 0 }; j < m; ++j) {
			char c{ s[j] };

			if (c == 'X') {
				a[i][j] = false;
				dr[i][j] = dj[i][j] = -1;
			}
			else {
				a[i][j] = true;
			}

			if (c == 'R') {
				R = { i, j };
				dr[i][j] = 1;
			}
			else if (c == 'J') {
				J = { i, j };
				dj[i][j] = 1;
			}
		}
	}
}

void Lee(Pair start, int d[105][105]) {
	queue<Pair> q;
	q.push(start);

	while (!q.empty()) {
		Pair p = q.front();
		int i{ p.first }, j{ p.second };
		q.pop();

		for (int k{ 0 }; k < 8; ++k) {
			int x{ i + dx[k] };
			int y{ j + dy[k] };

			if (x >= 0 && y >= 0 && x < n && y < m && a[x][y] && !d[x][y]) {
				d[x][y] = d[i][j] + 1;
				q.push({ x, y });
			}
		}
	}
}

void gaseste_drum() {
	int d_min{ 101 * 101 };
	Pair poz_min;

	for (int i{ 0 }; i < n; ++i)
		for (int j{ 0 }; j < m; ++j)
			if (dr[i][j] == dj[i][j] && dr[i][j] && dr[i][j] != -1 && dr[i][j] < d_min) {
				d_min = dr[i][j];
				poz_min = { i, j };
			}

	out << d_min << ' ' << poz_min.first + 1 << ' ' << poz_min.second + 1;
}

int main() {
	citeste();
	Lee(R, dr);
	Lee(J, dj);

	gaseste_drum();
}