Cod sursa(job #2952986)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 10 decembrie 2022 11:57:19
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <climits>
#include <queue>

using namespace std;

int n, m, ri, rj, ji, jj;

const int nmax = 1e2;

int r[nmax + 2][nmax + 2], ju[nmax + 2][nmax + 2];
char ch[nmax + 2][nmax + 2];

queue<pair<int, int>> q;

const int DIR = 4;
int dl[DIR] = {0, 1, 0, -1, -1, 1, -1, 1};
int dc[DIR] = {1, 0, -1, 0, -1, 1,  1, -1};

bool verif (int i, int j){
  if (i >= 1 && i <= n && j >= 1 && j <= m)
    return 1;
  return 0;
}

void lee(int st,int fn,int aux[nmax + 2][nmax + 2]){
  aux[st][fn] = 1;
  q.push({st, fn});

  while (!q.empty()){
    int lin = q.front().first;
    int col = q.front().second;
    q.pop();

    for (int i = 0; i < DIR; i++){
      int spreadl = lin + dl[i];
      int spreadc = col + dc[i];

      if (verif (spreadl, spreadc) && !aux[spreadl][spreadc])
        aux[spreadl][spreadc] = aux[lin][col] + 1, q.push({spreadl, spreadc});
    }
  }
}


int main(){

  ifstream fin ("rj.in");
  ofstream fout ("rj.out");

  fin >> n >> m;fin.get();
  string s;

  for (int i = 1; i <= n; i++){

    getline(fin, s);
    for (int j = 1; j <= m; j++){
      if (s[j - 1] == 'R')
        ri = i, rj = j;
      else if (s[j - 1] == 'J')
        ji = i, jj = j;
      else if (s[j - 1] == 'X')
        r[i][j] = ju[i][j] = -1;
    }
  }

  lee (ri, rj, r);
  lee (ji, jj, ju);

  int minn = INT_MAX;
  int soli, solj;
  soli = solj = -1;

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
      if (r[i][j] == ju[i][j] && (r[i][j] > 0 && ju[i][j] > 0))
        if (r[i][j] < minn){
          minn = ju[i][j];
          soli = i, solj = j;
        }
    }
  fout << minn << " " << soli << " " << solj;
  return 0;
}