Cod sursa(job #2034095)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 7 octombrie 2017 14:05:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");

int const nmax = 100;
char v[1 + nmax][1 + nmax];
struct Square{
  int x;
  int y;
};
int const iplus[8] = {0 ,0 , 1 ,1 ,1 ,-1 ,-1 ,-1};
int const jplus[8] = {1 ,-1 ,0 ,1, -1 ,0 ,1 , -1};

int n , m;
int distr[5 + nmax][5 + nmax];
int distj[5 + nmax][5 + nmax];

void bfs(){
  queue<Square> q;
  for(int i = 1 ; i <= n ;i++){
    for(int j = 1 ; j <= m ;j++){
      if(v[i][j] == 'R'){
        distr[i][j] = 1;
        q.push({i , j});
      } else{
        distr[i][j] = -1;
      }
    }
  }
  while(0 < q.size()){
    int x = q.front().x;
    int y = q.front().y;
    q.pop();
    for(int h = 0 ; h < 8 ;h++){
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(v[newx][newy] == ' ' && (distr[newx][newy] == -1 || distr[x][y] + 1 < distr[newx][newy] ) ){
        q.push({newx , newy});
        distr[newx][newy] = distr[x][y] + 1;
      }
    }
  }
  for(int i = 1 ; i <= n ;i++){
    for(int j = 1 ; j <= m ;j++){
      if(v[i][j] == 'J'){
        distj[i][j] = 1;
        q.push({i , j});
      } else{
        distj[i][j] = -1;
      }
    }
  }
  while(0 < q.size()){
    int x = q.front().x;
    int y = q.front().y;
    q.pop();
    for(int h = 0 ; h < 8 ;h++){
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(v[newx][newy] == ' ' && (distj[newx][newy] == -1 || distj[x][y] + 1 < distj[newx][newy] ) ){
        q.push({newx , newy});
        distj[newx][newy] = distj[x][y] + 1;
      }
    }
  }
}
int main()
{
  in>>n>>m;
  in>>noskipws;
  char c;
  for(int i = 1 ; i <= n ;i++){
    in>>c;///endline
    for(int j = 1 ; j <= m ;j++){
      in>>v[i][j];
      //cout<<v[i][j];
    }
    //cout<<'\n';
  }
  bfs();
  int smax = 1000000000;
  int x = 0, y = 0;
  for(int i = 1 ; i <= n ;i++){
    for(int j = 1 ; j <= m ;j++){
      if(distj[i][j] == distr[i][j] && 0 < distj[i][j]){
        if(distj[i][j] < smax){
          smax = distj[i][j];
          x = i;
          y = j;
        }
      }
    }
  }
  out<<smax<<" "<<x<<" "<<y;
  return 0;
}