Cod sursa(job #2517369)

Utilizator lucametehauDart Monkey lucametehau Data 3 ianuarie 2020 14:06:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <queue>
#define SH short

using namespace std;

ifstream cin ("rj.in");
ofstream cout ("rj.out");

struct Point {
  SH x, y;
};

SH n, m;
char ch;
Point R, J;

char mat[105][105];
SH dp[2][105][105];
queue <Point> q;
SH dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
SH dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

void lee(Point st, SH ok) {
  q.push(st);
  dp[ok][st.x][st.y] = 1;
  while(!q.empty()) {
    Point p = q.front();
    q.pop();
    for(int i = 0; i < 8; i++) {
      Point newp = {p.x + dx[i], p.y + dy[i]};
      if(newp.x >= 1 && newp.x <= n && newp.y >= 1 && newp.y <= m && mat[newp.x][newp.y] != 'X' && !dp[ok][newp.x][newp.y]) {
        dp[ok][newp.x][newp.y] = dp[ok][p.x][p.y] + 1;
        q.push(newp);
      }
    }
  }
}

int main() {
  cin >> n >> m >> ws;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin.get(ch);
      mat[i][j] = ch;
      if(ch == 'R')
        R = {i, j};
      else if(ch == 'J')
        J = {i, j};
    }
    cin >> ws;
  }
  lee(R, 0);
  lee(J, 1);
  int tmn = (SH)1e5, l = 0, c = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(dp[0][i][j] && dp[0][i][j] == dp[1][i][j]) {
        if(dp[1][i][j] < tmn) {
          tmn = dp[1][i][j];
          l = i;
          c = j;
        }
      }
    }
  }
  cout << tmn << " " << l << " " << c;
  return 0;
}