Cod sursa(job #2293572)

Utilizator raulsomesanRaul Somesan raulsomesan Data 1 decembrie 2018 11:12:23
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <queue>

using namespace std;

struct point{
    int x, y;
};
int a[105][105], b[105][105];

queue <point> q;
queue <point> q2;

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
  freopen("rj.in", "r", stdin);
  freopen("rj.out", "w", stdout);
  int n, m, x = 0, y, i, j, x1, x2, y1, y2, min1, el;
  char c;
  scanf("%d%d ", &n, &m);
  for (i = 0; i <= m + 1; i ++)
      a[n + 1][i] = a[0][i] = b[0][i] = b[n + 1][i] = -1;
  for (i = 0; i <= n + 1; i ++)
      a[i][m + 1] = a[i][0] = b[i][0] = b[i][m + 1] = -1;
  for (i = 1; i <= n; i ++){
    for (j = 1; j <= m; j ++){
      c = getc(stdin);
      if (c == 'J')
        x1 = i, y1 = j;
      else if (c == 'X')
        a[i][j] = b[i][j] = -1;
      else if (c == 'R')
        x2 = i, y2 = j;
      else
        x ++;
    }
    getc(stdin);
  }
  point f, temp;
  temp.x = x1;
  temp.y = y1;
  q.push(temp);
  a[x1][y1] = 1;
  while (!q.empty()){
    f = q.front();
    q.pop();
    for (i = 0; i < 8; i ++){
      temp.x = f.x + dx[i];
      temp.y = f.y + dy[i];
      if (a[temp.x][temp.y] == 0){
        q.push(temp);
        a[temp.x][temp.y] = a[f.x][f.y] + 1;
      }
    }
  }
  temp.x = x2;
  temp.y = y2;
  q2.push(temp);
  b[x2][y2] = 1;
  while (!q2.empty()){
    f = q2.front();
    q2.pop();
    for (i = 0; i < 8; i ++){
      temp.x = f.x + dx[i];
      temp.y = f.y + dy[i];
      if (b[temp.x][temp.y] == 0){
        q2.push(temp);
        b[temp.x][temp.y] = b[f.x][f.y] + 1;
      }
    }
  }
  min1 = 99999999;
  for (i = 1; i <= n; i ++){
    for (j = 1; j <= m; j ++)
      if (a[i][j] == b[i][j] && a[i][j] < min1 && a[i][j] > 0)
        min1 = a[i][j], x1 = i, y1 = j;
  }
  printf("%d %d %d", min1, x1, y1);
  return 0;
}