Cod sursa(job #1982993)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 20 mai 2017 21:28:19
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <queue>
#define INF 1e9
#define BARIERA -1
#define MAX 105
using namespace std;

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

bool isOK(pair<int, int> p, int n, int m){
  int x = p.first, y = p.second;
  return x > 0 and x <= n and y > 0 and y <= m;
}

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

  int n, m, ar[MAX][MAX], aj[MAX][MAX];
  pair<int, int> rom, jul;
  cin >> n >> m;
  cin.get();

  for(int i = 1; i <= n; i++){
    char c[MAX];
    cin.getline(c,MAX);
    for(int j = 1; j <= m; j++){
      if(c[j - 1] == 'X'){
        ar[i][j] = BARIERA;
        aj[i][j] = BARIERA;
      }
      else if(c[j - 1] == 'R'){
        ar[i][j] = INF;
        aj[i][j] = INF;
        rom.first = i;
        rom.second = j;
      }
      else if(c[j - 1] == 'J'){
        ar[i][j] = INF;
        aj[i][j] = INF;
        jul.first = i;
        jul.second = j;
      }
      else{
        ar[i][j] = INF;
        aj[i][j] = INF;
      }
    }
  }

  queue< pair< int, int > > q;
  ar[rom.first][rom.second] = 1;
  q.push(rom);

  while(!q.empty()){
    pair<int, int> now = q.front();
    for(int i = 0; i < 8; i++){
      pair<int, int> next;
      next.first = now.first + dx[i];
      next.second = now.second +dy[i];
      if(isOK(next, n, m)){
        if(ar[next.first][next.second] != INF)
          continue;
        else{
          ar[next.first][next.second] = ar[now.first][now.second]+1;
          q.push(next);
        }
      }
    }
    q.pop();
  }

  aj[jul.first][jul.second] = 1;
  q.push(jul);

  while(!q.empty()){
    pair<int, int> now = q.front();
    for(int i = 0; i < 8; i++){
      pair<int, int> next;
      next.first = now.first + dx[i];
      next.second = now.second +dy[i];
      if(isOK(next, n, m)){
        if(aj[next.first][next.second] != INF)
          continue;
        else{
          aj[next.first][next.second] = aj[now.first][now.second]+1;
          q.push(next);
        }
      }
    }
    q.pop();
  }
  int x, y;
  int MIN = 1e8;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
      if(ar[i][j] == -1)
        continue;
      if(aj[i][j] == -1)
        continue;
      if(ar[i][j] == aj[i][j])
        if(ar[i][j] < MIN)
        {
          MIN = ar[i][j];
          x = i;
          y = j;
        }
    }
  cout << MIN << ' ' << x << ' ' << y <<'\n';

  return 0;
}