Cod sursa(job #2568222)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 3 martie 2020 21:29:55
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<cstdio>
#include<queue>
struct point{
  int x , y;
};
std :: queue<point>q;
int dx[] = {0 , -1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
int dy[] = {0 , 0 , 1 , 1, 1 , 0 , -1 ,-1 ,-1};
char v[101][101];
int distR[101][101];
int distJ[101][101];
point romeo , julieta;
const int INF = 100000;
int main()
{
  int n , m;
  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')
      {
        romeo.x = i;
        romeo.y = j;
      }
      if(v[i][j] == 'J')
      {
        julieta.x = i;
        julieta.y = j;
      }
      distR[i][j] = INF;
      distJ[i][j] = INF;
    }
    scanf("%c");
  }
  q.push(romeo);
  distR[romeo.x][romeo.y] = 0;
  while(q.empty() == false)
  {
    point aux = q.front();
    q.pop();
    for(int d = 1; d <= 8 ; d ++)
    {
      if(aux.x + dx[d] > 0 && aux.x + dx[d] <= n && aux.y + dy[d] > 0 && aux.y + dy[d] <= m && distR[aux.x + dx[d]][aux.y + dy[d]] > distR[aux.x][aux.y] + 1 && v[aux.x + dx[d]][aux.y + dy[d]] == ' ')
      {
        distR[aux.x + dx[d]][aux.y + dy[d]] = distR[aux.x][aux.y] + 1;
        q.push({aux.x + dx[d] ,  aux.y + dy[d]});
      }
    }
  }
  q.push(julieta);
  distJ[julieta.x][julieta.y] = 0;
  while(q.empty() == false)
  {
    point aux = q.front();
    q.pop();
    for(int d = 1; d <= 8 ; d ++)
    {
      if(aux.x + dx[d] > 0 && aux.x + dx[d] <= n && aux.y + dy[d] > 0 && aux.y + dy[d] <= m && distJ[aux.x + dx[d]][aux.y + dy[d]] > distJ[aux.x][aux.y] + 1 && v[aux.x + dx[d]][aux.y + dy[d]] == ' ')
      {
        distJ[aux.x + dx[d]][aux.y + dy[d]] = distJ[aux.x][aux.y] + 1;
        q.push({aux.x + dx[d] ,  aux.y + dy[d]});
      }
    }
  }
  int minim = INF, minx , miny;
  for(int i = 1; i <= n ; i ++)
    for(int j = 1; j <= m; j ++)
  {
    if(distR[i][j] == distJ[i][j] && distR[i][j] < minim)
    {
      minim = distR[i][j];
      minx = i;
      miny = j;
    }
  }
  printf("%d %d %d" , minim + 1 , minx , miny);
  return 0;

}