Cod sursa(job #3150376)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 16 septembrie 2023 10:58:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#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];

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

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 = 0;i < 4;i++) {
      Point to = {from.x + dirX[i], from.y + dirY[i]};
      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);
  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;
}