Cod sursa(job #2102796)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 9 ianuarie 2018 15:03:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <queue>

const int MAXN = 1e2;
const int INF = 2e9;
#define NUM_DIR 8

struct Cd {
  int x, y;
};

int delta[NUM_DIR][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}},
    a[MAXN][MAXN], b[MAXN][MAXN];
char mt[MAXN][MAXN];
std::queue <Cd> q;

int main() {
  int n, m, sr, dr, sj, dj, l, c, x, y, ans, ansx, ansy;
  Cd cr;
  FILE *f = fopen("rj.in", "r");
  fscanf(f, "%d%d\n", &n, &m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      a[i][j] = b[i][j] = INF;
      fscanf(f, "%c", &mt[i][j]);
      if (mt[i][j] == 'R') {
        sr = i;
        dr = j;
      } else if (mt[i][j] == 'J') {
        sj = i;
        dj = j;
      }
    }
    fgetc(f);
  }
  fclose(f);
  q.push({sr, dr});
  a[sr][dr] = 1;
  while (!q.empty()) {
    cr = q.front();
    q.pop();
    l = cr.x;
    c = cr.y;
    for (int i = 0; i < NUM_DIR; ++i) {
      x = l + delta[i][0];
      y = c + delta[i][1];
      if (0 <= x && 0 <= y && x < n && y < m && mt[x][y] != 'X' && a[x][y] == INF) {
        a[x][y] = a[l][c] + 1;
        q.push({x, y});
      }
    }
  }
  q.push({sj, dj});
  b[sj][dj] = 1;
  while (!q.empty()) {
    cr = q.front();
    q.pop();
    l = cr.x;
    c = cr.y;
    for (int i = 0; i < NUM_DIR; ++i) {
      x = l + delta[i][0];
      y = c + delta[i][1];
      if (0 <= x && 0 <= y && x < n && y < m && mt[x][y] != 'X' && b[x][y] == INF) {
        b[x][y] = b[l][c] + 1;
        q.push({x, y});
      }
    }
  }
  ans = INF;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (a[i][j] == b[i][j] && ans > a[i][j] && a[i][j] != INF) {
        ans = a[i][j];
        ansx = i + 1;
        ansy = j + 1;
      }
    }
  }
  f = fopen("rj.out", "w");
  fprintf(f, "%d %d %d\n", ans, ansx, ansy);
  fclose(f);
  return 0;
}