Cod sursa(job #2293756)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 1 decembrie 2018 15:36:44
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
# include<cstdio>
# include<queue>
struct lee
{
  int x , y , dist;
};
std :: queue<lee>q;
const int NMAX = 100;
int distanteromeo[NMAX + 1][NMAX + 1];
int distantejulieta[NMAX + 1][NMAX + 1];
int v[NMAX + 1][NMAX + 1];
int dx[] = {0 , -1 , 0 ,1 , 0};
int dy[] = {0 , 0 , 1 , 0 , -1};
int main()
{
  int n , m , romeox , romeoy , julietax , julietay , ri , rj;
  freopen("rj.in" , "r" , stdin);
  freopen("rj.out" , "w" , stdout);
  scanf("%d%d ", &n , &m);
  for(int i = 1; i <= n ; i ++){
    for(int j = 1; j <= m; j ++)
    {
      scanf("%c" , &v[i][j]);
      if(v[i][j] == 'R')
      {
        romeox = i;
        romeoy = j;
      }
      if(v[i][j] == 'J')
      {
        julietax = i;
        julietay = j;
      }
      distanteromeo[i][j] = distantejulieta[i][j] = 999999999;
    }
    scanf("\n");
  }
  q.push({romeox , romeoy , 0});
  distanteromeo[romeox][romeoy] = 0;
  while(q.empty() == false)
  {
    lee aux;
    aux = q.front();
    q.pop();
    for(int i = 1; i <= 4 ; i ++)
    {
      lee next;
      next.x = aux.x + dx[i];
      next.y = aux.y + dy[i];
      next.dist = distanteromeo[aux.x][aux.y] + 1;
      if(v[next.x][next.y] == ' ' && distanteromeo[next.x][next.y] > next.dist)
      {
        distanteromeo[next.x][next.y] = next.dist;
        q.push(next);
      }
    }
  }
  q.push({julietax , julietay , 0});
  distantejulieta[julietax][julietay] = 0;
  while(q.empty() == false)
  {
    lee aux;
    aux = q.front();
    q.pop();
    for(int i = 1; i <= 4 ; i ++)
    {
      lee next;
      next.x = aux.x + dx[i];
      next.y = aux.y + dy[i];
      next.dist = distantejulieta[aux.x][aux.y] + 1;
      if(v[next.x][next.y] == ' ' && distantejulieta[next.x][next.y] > next.dist)
      {
        distantejulieta[next.x][next.y] = next.dist;
        q.push(next);
      }
    }
  }
  int mindist = 100000000;
  for(int i = 1; i <= n ; i ++)
    for(int j = 1 ; j <= m ; j ++)
  {
    if(distantejulieta[i][j] == distanteromeo[i][j] && distanteromeo[i][j] != 0)
    {
      mindist = std :: min (mindist , distantejulieta[i][j]);
      if(mindist == distantejulieta[i][j])
      {
        ri = i;
        rj = j;
      }
    }
  }
  printf("%d %d %d" , mindist , ri , rj);
  return 0;
}