Cod sursa(job #2193435)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 10 aprilie 2018 09:41:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <queue>

const int MAX_N = 100;

struct Coord {
  int x;
  int y;
};

int n, m;
char a[1 + MAX_N][5 + MAX_N];
int dist[2][1 + MAX_N][1 + MAX_N];
bool viz[1 + MAX_N][1 + MAX_N];
int dirLin[] = {-1, 1, 0, 0, -1, 1, 1, -1};
int dirCol[] = {0, 0, 1, -1, 1, 1, -1, -1};

void initViz() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      viz[i][j] = false;
    }
  }
}

bool valid(int x, int y) {
  return 1 <= x && x <= n && 1 <= y && y <= m && a[x][y] != 'X';
}

void bfs(int start, int startX, int startY) {
  initViz();
  std::queue<Coord> q;
  q.push({startX, startY});
  viz[startX][startY] = true;
  dist[start][startX][startY] = 0;
  while (!q.empty()) {
    Coord front = q.front();
    q.pop();
    int x = front.x;
    int y = front.y;
    for (int dir = 0; dir < 8; dir++) {
      int newX = x + dirLin[dir];
      int newY = y + dirCol[dir];
      if (valid(newX, newY) && !viz[newX][newY]) {
        q.push({newX, newY});
        viz[newX][newY] = true;
        dist[start][newX][newY] = dist[start][x][y] + 1;
      }
    }
  }
}

int main() {
  freopen("rj.in", "r", stdin);
  freopen("rj.out", "w", stdout);
  
  int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  scanf("%d%d\n", &n, &m);
  for (int i = 1; i <= n; i++) {
    gets(a[i] + 1);
    for (int j = 1; j <= m; j++) {
      if (a[i][j] == 'R') {
        x1 = i;
        y1 = j;
      } else if (a[i][j] == 'J') {
        x2 = i;
        y2 = j;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dist[0][i][j] = -1;
      dist[1][i][j] = -1;
    }
  }
  bfs(0, x1, y1);
  bfs(1, x2, y2);
  int tMin = 2000000000;
  int x, y;
  x = y = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (dist[0][i][j] != -1 && dist[0][i][j] == dist[1][i][j] && dist[0][i][j] < tMin) {
        tMin = dist[0][i][j];
        x = i;
        y = j;
      }
    }
  }
  printf("%d %d %d\n", 1 + tMin, x, y);
  return 0;
}