Cod sursa(job #2929367)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 25 octombrie 2022 18:30:46
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <climits>
#include <queue>
#define NMAX 100
#define DIR 8

using namespace std;

int n, m, ri, rj, ji, jj;
int r[NMAX + 2][NMAX + 2], ju[NMAX + 2][NMAX + 2];
char ch[NMAX + 2][NMAX + 2];
queue<pair<int, int>> q;

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;
}