Cod sursa(job #2667155)

Utilizator MicuMicuda Andrei Micu Data 2 noiembrie 2020 22:48:05
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <utility>

using namespace std;

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

const int MAX = 101;

int ox[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int oy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
// (5, 4)
// 0: (4, 3) -> NV
// 1: (5, 3) -> V
// 2: (6, 3) -> SV
// 3: (4, 4) -> N
// 4: (6, 4) -> S
// 5: (4, 5) -> NE
// 6: (5, 5) -> E
// 7: (6, 5) -> SE

int n, m, mat[MAX][MAX][2];
queue<pair<int, int>> q;

bool isValid(int x, int y, int rj)
{
  return (x >= 0 && y >= 0 && x < n && y < m && mat[x][y][rj] == -1);
}

void BFS(int rj, int root_x, int root_y)
{
  mat[root_x][root_y][rj] = 0;

  q.push(make_pair(root_x, root_y));
  while (!q.empty())
  {
    int curr_x = q.front().first;
    int curr_y = q.front().second;
    q.pop();
    for (int i = 0; i < 8; i++)
    {
      int next_x = curr_x + ox[i];
      int next_y = curr_y + oy[i];
      if (isValid(next_x, next_y, rj))
      {
        mat[next_x][next_y][rj] = mat[curr_x][curr_y][rj] + 1;
        q.push(make_pair(next_x, next_y));
      }
    }
  }
}

int main()
{
  int rx, ry, jx, jy;
  in >> n >> m;
  in.get();
  for (int i = 0; i < n; i++)
  {
    for (int k = 0; k < m; k++)
    {
      char x;
      in.get(x);
      if (x == 'X')
      {
        mat[i][k][0] = -2;
        mat[i][k][1] = -2;
      }
      else
      {
        mat[i][k][0] = -1;
        mat[i][k][1] = -1;
      }

      if (x == 'R')
      {
        rx = i;
        ry = k;
      }

      if (x == 'J')
      {
        jx = i;
        jy = k;
      }
    }
    in.get();
  }

  BFS(0, rx, ry);
  BFS(1, jx, jy);

  int tmin = 10001;
  int rez_x, rez_y;
  for (int i = 0; i < n; i++)
  {
    for (int k = 0; k < m; k++)
    {
      if (mat[i][k][0] == mat[i][k][1] && mat[i][k][0] >= 0 && mat[i][k][0] < tmin)
      {
        tmin = mat[i][k][0];
        rez_x = i;
        rez_y = k;
      }
    }
  }

  out << tmin + 1 << ' ' << rez_x + 1 << ' ' << rez_y + 1;
  return 0;
}