Cod sursa(job #1337821)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 9 februarie 2015 15:43:45
Problema Rj Scor 100
Compilator cpp Status done
Runda simulareoji2015cl10 Marime 1.82 kb
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

const int MAXN = 105;

char m[MAXN][MAXN];
int vizr[MAXN][MAXN], vizj[MAXN][MAXN], N, M;
queue<int> qx, qy;
int diri[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirj[] = {0, 1, 1, 1, 0, -1, -1, -1};

bool in_matrix(int x, int y) {
   if(x > 0 && y > 0 && x <= N && y <= M)
      return true;
   return false;
}

void BFS(int x, int y, int viz[MAXN][MAXN]) {
   qx.push(x);
   qy.push(y);
   viz[x][y] = 1;
   while(!qx.empty()) {
      int xc = qx.front();
      int yc = qy.front();
      qx.pop();
      qy.pop();
      for(int k = 0; k < 8; ++k) {
         if(m[xc + diri[k]][yc + dirj[k]] != 'X' && !viz[xc + diri[k]][yc + dirj[k]] && in_matrix(xc + diri[k], yc + dirj[k])) {
            qx.push(xc + diri[k]);
            qy.push(yc + dirj[k]);
            viz[xc + diri[k]][yc + dirj[k]] = viz[xc][yc] + 1;
         }
      }
   }
}

int main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");
    int xr = 0, yr = 0, xj = 0, yj = 0;
    string s;
    cin >> N >> M;
    getline(cin, s);
    for(int i = 1; i <= N; ++i) {
      getline(cin, s);
      for(int j = 0; j < M; ++j) {
         m[i][j + 1] = s[j];
         if(m[i][j] == 'R') {
            xr = i;
            yr = j;
         }
         if(m[i][j] == 'J') {
            xj = i;
            yj = j;
         }
      }
    }
    BFS(xr, yr, vizr);
    BFS(xj, yj, vizj);
    int tmin = N * M, ansx = 0, ansy = 0;
    for(int i = 1; i <= N; ++i)
      for(int j = 1; j <= M; ++j) {
         if(vizr[i][j] && vizr[i][j] == vizj[i][j] && vizr[i][j] < tmin) {
            tmin = vizr[i][j];
            ansx = i;
            ansy = j;
         }
      }
    cout << tmin << ' ' << ansx << ' ' << ansy << '\n';
    return 0;
}