Pagini recente » Cod sursa (job #1575046) | Cod sursa (job #1304006) | Cod sursa (job #368466) | Cod sursa (job #1702568) | Cod sursa (job #3150380)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int const INF = 1e9+7;
int n, m;
int const NMAX = 175;
int dist[2][1 + NMAX][1 + NMAX];
bool tree[1 + NMAX][1 + NMAX];
struct Point {
int x;
int y;
};
bool isValid(Point a) {
return (1 <= a.x && a.x <= n && 1 <= a.y && a.y <= m && tree[a.x][a.y] == false);
}
void BFS(Point start, int type) {
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
dist[type][i][j] = INF;
}
}
queue <Point> q;
q.push(start);
dist[type][start.x][start.y] = 0;
while(!q.empty()) {
Point from = q.front();
q.pop();
for(int i = -1;i <= 1;i++) {
for(int j = -1;j <= 1;j++) {
if(!(i == 0 && j == 0)) {
Point to = {from.x + i, from.y + j};
if(isValid(to) && dist[type][from.x][from.y] + 1 < dist[type][to.x][to.y]) {
dist[type][to.x][to.y] = dist[type][from.x][from.y] + 1;
q.push(to);
}
}
}
}
}
}
int main() {
char ch;
in >> n >> m;
in.get(ch);
Point Romeo, Julieta;
for(int i = 1;i <= n;i++) {
int j = 1;
while(in.get(ch) && ch != '\n') {
if(ch == 'X') {
tree[i][j] = true;
}
if(ch == 'R') {
Romeo = {i, j};
}
if(ch == 'J') {
Julieta = {i, j};
}
j++;
}
}
/*
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
out << tree[i][j] << ' ';
}
out << '\n';
}
*/
BFS(Romeo, 0);
BFS(Julieta, 1);
/*
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(tree[i][j]) {
out << "X ";
}else if(dist[0][i][j] < INF){
out << dist[0][i][j] << ' ';
}else {
out << ". ";
}
}
out << '\n';
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(tree[i][j]) {
out << "X ";
}else if(dist[1][i][j] < INF){
out << dist[1][i][j] << ' ';
}else {
out << ". ";
}
}
out << '\n';
}
*/
Point ans = {0, 0};
dist[0][0][0] = INF;
dist[1][0][0] = INF;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(dist[0][i][j] == dist[1][i][j] && dist[0][ans.x][ans.y] + dist[1][ans.x][ans.y] > dist[0][i][j] + dist[1][i][j]) {
ans = {i, j};
}
}
}
out << ans.x << ' ' << ans.y << ' ' << (dist[0][ans.x][ans.y] + dist[1][ans.x][ans.y]) / 2 << '\n';
return 0;
}