Cod sursa(job #2809713)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 27 noiembrie 2021 13:56:16
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

#define all(a) a.begin(), a.end()
#define range(a, l, r) a.begin() + l, a.begin() + r
#define aall(a, n) a + 1, a + 1 + n
#define arange(a, l, r) a + l, a + r
	
#define maxself(a, b) a = std::max(a, b);
#define minself(a, b) a = std::min(a, b);

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")

#include <iostream>
#include <fstream>
#include <queue>
#include <string>

const int NMAX = 100;

//                  N, NE,  E, SE,  S, SW,  W, NW
const int d8i[] = {-1, -1,  0,  1,  1,  1,  0, -1};
const int d8j[] = { 0,  1,  1,  1,  0, -1, -1, -1};

int n, m;

int rMap[1 + NMAX][1 + NMAX];
int rsi, rsj;

int jMap[1 + NMAX][1 + NMAX];
int jsi, jsj;

std::queue<std::pair<int, int>> q;

inline bool inside(int i, int j) {
  return 1 <= i && i <= n && 1 <= j && j <= m;
}

int main() {
  inout("rj");

  in >> n >> m;
  in.get();

  for (int i = 1; i <= n; ++i) {
    std::string line;
    std::getline(in, line);

    for (int j = 1; j <= m; ++j) {
      char bruh = line[j - 1];

      if (bruh == 'X') {
        rMap[i][j] = -1;
        jMap[i][j] = -1;
      }
      else if (bruh == ' ') {
        rMap[i][j] = 0;
        jMap[i][j] = 0;
      }
      else if (bruh == 'R') {
        rMap[i][j] = 1;
        jMap[i][j] = 0;

        rsi = i, rsj = j;
      }
      else if (bruh == 'J') {
        rMap[i][j] = 0;
        jMap[i][j] = 1;

        jsi = i, jsj = j;
      }
    }
  }

  q.emplace(rsi, rsj);
  while (!q.empty()) {
    auto node = q.front();
    q.pop();

    for (int dir = 0; dir < 8; ++dir) {
      int i = node.first + d8i[dir];
      int j = node.second + d8j[dir];

      if (!inside(i, j) || (rMap[i][j] != 0 && rMap[i][j] <= rMap[node.first][node.second] + 1))
        continue;

      rMap[i][j] = rMap[node.first][node.second] + 1;
      q.emplace(i, j);
    }
  }

  q.emplace(jsi, jsj);
  while (!q.empty()) {
    auto node = q.front();
    q.pop();

    for (int dir = 0; dir < 8; ++dir) {
      int i = node.first + d8i[dir];
      int j = node.second + d8j[dir];

      if (!inside(i, j) || (jMap[i][j] != 0 && jMap[i][j] <= jMap[node.first][node.second] + 1))
        continue;

      jMap[i][j] = jMap[node.first][node.second] + 1;
      q.emplace(i, j);
    }
  }

  int best = 1e9 + 7;
  int iBest = -1, jBest = -1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (rMap[i][j] == jMap[i][j] && rMap[i][j] >= 1 && rMap[i][j] < best) {
        iBest = i;
        jBest = j;
        best = rMap[i][j];
      }
    }
  }

  out << best << ' ' << iBest << ' ' << jBest << '\n';

  return 0;
}