Cod sursa(job #2209043)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 1 iunie 2018 16:21:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <cstring>
#include <queue>

#define MAXN 100
#define INF 2000000000

using namespace std;

struct Coordonate
{
  int x, y;
};

int n, m;

char mat[MAXN+5][MAXN+5];
int timp[5][MAXN+5][MAXN+5];
bool viz[MAXN+5][MAXN+5];

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

bool valid( int i, int j )
{
  return ((1<=i && i<=n) && (1<=j && j<=m) && mat[i][j]!='X');
}

void bfs( int f, int fx, int fy )
{
  queue<Coordonate>q;
  q.push(Coordonate{fx,fy});

  viz[fx][fy]=1;
  timp[f][fx][fy]=0;

  while( !q.empty() )
  {
    Coordonate first=q.front();
    q.pop();

    int x=first.x, y=first.y;

    for( int k=0;k<8;k++ )
    {
      int i=x+dlin[k], j=y+dcol[k];

      if( valid(i,j) && !viz[i][j] )
      {
        q.push(Coordonate{i,j});

        viz[i][j]=1;
        timp[f][i][j]=timp[f][x][y]+1;
      }
    }
  }
}

int main()
{
  freopen( "rj.in", "r", stdin );
  freopen( "rj.out", "w", stdout );

  int x1=0, y1=0, x2=0, y2=0;

  scanf( "%d%d\n", &n, &m );

  for( int i=1;i<=n;i++ )
  {
    gets(mat[i]+1);

    for( int j=1;j<=m;j++ )
      if( mat[i][j]=='R' )
      {
        x1=i;
        y1=j;
      }
      else
        if( mat[i][j]=='J' )
        {
          x2=i;
          y2=j;
        }
  }

  for( int i=1;i<=n;i++ )
    for( int j=1;j<=m;j++ )
      timp[0][i][j]=timp[1][i][j]=-1;

  bfs(0,x1,y1);

  for( int i=1;i<=n;i++ )
    for( int j=1;j<=m;j++ )
      viz[i][j]=0;

  bfs(1,x2,y2);

  int t=INF, x=0, y=0;

  for( int i=1;i<=n;i++ )
    for( int j=1;j<=m;j++ )
      if( timp[0][i][j]!=-1 && timp[0][i][j]==timp[1][i][j] && timp[0][i][j]<t )
      {
        t=timp[0][i][j];
        x=i;
        y=j;
      }

  printf( "%d %d %d\n", t+1, x, y );

  return 0;
}