Cod sursa(job #3150380)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 16 septembrie 2023 11:23:27
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#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;
}