Cod sursa(job #2215585)

Utilizator PetyAlexandru Peticaru Pety Data 22 iunie 2018 19:05:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
using namespace std;

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

int dl[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
int dc[8] = {0, -1, 1, 0, -1, 1, -1, 1};

bool f[102][102];
int n, m, a[102][102], b[102][102], x1, y1, x2, y2, tmin, l, c;
char ch[102][102];

int main()
{
  fin >> n >> m;
  fin.get();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      fin.get(ch[i][j]);
      if (ch[i][j] == 'R')
        x1 = i, y1 = j;
      if (ch[i][j] == 'J')
        x2 = i, y2 = j;
    }
    fin.get();
  }
  a[x1][y1] = f[x1][y1] = 1;
  queue<pair<int, int> >q;
  q.push({x1, y1});
  while (!q.empty()) {
    pair<int, int>p = q.front();
    q.pop();
    for (int i = 0; i < 8; i++) {
      int x = p.first + dl[i];
      int y = p.second + dc[i];
      if (x >= 1 && x <= n && y >= 1 && y <= m && !f[x][y] && ch[x][y] == ' ') {
        f[x][y] = 1;
        a[x][y] = 1 + a[p.first][p.second];
        q.push({x, y});
      }
    }
  }
  memset(f, 0, sizeof(f));
  b[x2][y2] = f[x2][y2] = 1;
  q.push({x2, y2});
  while (!q.empty()) {
    pair<int, int>p = q.front();
    q.pop();
    for (int i = 0; i < 8; i++) {
      int x = p.first + dl[i];
      int y = p.second + dc[i];
      if (x >= 1 && x <= n && y >= 1 && y <= m && !f[x][y] && ch[x][y] == ' ') {
        f[x][y] = 1;
        b[x][y] = 1 + b[p.first][p.second];
        q.push({x, y});
      }
    }
  }
  tmin = INT_MAX;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      if (a[i][j] == b[i][j] && tmin > a[i][j] && a[i][j] > 0) {
        tmin = a[i][j];
        l = i;
        c = j;
      }
    }
  fout << tmin << " " << l << " " << c;
	return 0;
}