Cod sursa(job #2244576)

Utilizator AxellbenCretu Alexandru Axellben Data 23 septembrie 2018 09:42:16
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <math.h>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

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

int n, m, ORAS_R[105][105], ORAS_J[105][105], Rx, Ry, Jx, Jy;

int drow[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dcol[] = {-1, 0, 1, -1, 1, -1, 0, 1};

queue<pair<int, int>> coada;

void citire() {
  f >> n >> m;
  char aux[105];
  f.getline(aux, 105);
  for (int row = 0; row < n; row++) {
    f.getline(aux, 105);
    for (int col = 0; col < m; col++) {
      if (aux[col] == 'X') {
        ORAS_R[row][col] = -1;
        ORAS_J[row][col] = -1;
      } else if (aux[col] == 'R') {
        Rx = row;
        Ry = col;
      } else if (aux[col] == 'J') {
        Jx = row;
        Jy = col;
      }
    }
  }
}

bool isValid(int x, int y, int ORAS[][105]) {
  if (x < 0 || y < 0 || x > n || y > m) {  // Daca mai suntem in oras
    return false;
  }
  if (ORAS[x][y] == -1) {  // Daca intalnim un obstacol
    return false;
  }
  return true;
}

void LEE(int start_x, int start_y, int ORAS[][105]) {
  int x, y, next_x, next_y;
  ORAS[start_x][start_y] = 1;
  coada.push(make_pair(start_x, start_y));
  while (!coada.empty()) {
    x = coada.front().first;   // Extarge x din primul element al cozii
    y = coada.front().second;  // Extarge y din primul element al cozii
    for (int vecin = 0; vecin < 8; vecin++) {
      next_x = x + drow[vecin];
      next_y = y + dcol[vecin];
      if (isValid(next_x, next_y, ORAS) && ORAS[next_x][next_y] == 0) {
        ORAS[next_x][next_y] = ORAS[x][y] + 1;
        coada.push(make_pair(next_x, next_y));
      }
    }
    coada.pop();
  }
}

void printCity(int ORAS[][105]) {
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < m; col++) {
      g << ORAS[row][col] << " ";
    }
    g << '\n';
  }
}

int main() {
  citire();
  LEE(Rx, Ry, ORAS_R);
  LEE(Jx, Jy, ORAS_J);
  // g << "ROMEO:" << '\n';
  // printCity(ORAS_R);
  // g << "\nJULIETA:\n";
  // printCity(ORAS_J);
  int dmin = 2000000000, Dx, Dy;

  // g << ceil(ORAS_R[Jx][Jy] / 2.0) << ' ';
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < m; col++) {
      if (ORAS_R[row][col] != -1 && ORAS_R[row][col] == ORAS_J[row][col]) {
        if (ORAS_R[row][col] < dmin) {
          dmin = ORAS_R[row][col];
          Dx = row;
          Dy = col;
        }
      }
    }
  }
  g << dmin << ' ' << Dx + 1 << ' ' << Dy + 1;
  // cout << ORAS_R[Jx][Jy] << " " << ORAS_J[Rx][Ry];

  return 0;
}

/*

5 5
 XX
X R X
X XXJ
X X X
X   X







5 5
R XX
X X J
X XX
X X
X   X
*/