Cod sursa(job #1994407)

Utilizator VarticeanNicolae Varticean Varticean Data 24 iunie 2017 21:18:35
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <string>
#include <queue>
using namespace std;
         ifstream in("rj.in");
         ofstream out("rj.out");
int A[105][105], B[105][105],N,M;
queue < pair<int, int> > Q ;
int di[8] = {0,0,1,1,1,-1,-1,-1};
int dj[8] = {1,-1,-1,0,1,-1,0,1};
string s;
int xj, yj, xr, yr;
void read()
{
    in>>N>>M;
    getline(in,s);
    for( int i=1; i<=N; i++)
    {
        getline(in,s);
        for(int j=0; j<M; j++)
    {
            if(s[j] == 'X' ) {A[i][j+1]=-1; B[i][j+1]=-1;}
            if(s[j] == 'J') {  xj=i; yj=j+1; A[i][j+1]=1;}
            if(s[j] == 'R') {  xr=i; yr=j+1; B[i][j+1]=1;}
    }

    }
}
bool OK(int i, int j, int C[][105] )
{
   if( i<1 || j<1 || i>N || j>M ) return false ;
   if ( C[i][j] == -1 ) return false ;
     return true ;
}
void Lee( int startx, int starty,int C[][105])
{
    int i,j,i_next,j_next;
    Q.push(make_pair(startx,starty));
    while( !Q.empty() )
    {
        i = Q.front().first;
        j = Q.front().second;

        Q.pop();
    for( int dr=0; dr<8; dr++)
    {
        i_next=i+di[dr];
        j_next=j+dj[dr];
        if( OK(i_next, j_next, C ) && !C[i_next][j_next] )
        {
            C[i_next][j_next]=C[i][j]+1;
            Q.push(make_pair(i_next,j_next));
        }
    }
    }
}

int main()
{

     read();
     Lee(xj,yj, A);
     Lee(xr,yr,B);
     int minim=1<<30 ;
      for( int i=1; i<=N; i++)
      {
          for(int j=1; j<=M; j++)
          if (A[i][j]==B[i][j] && A[i][j] >0  && A[i][j]<minim  ) minim =A[i][j];
      }
      for( int i=1; i<=N; i++)
      {
          bool ok=false ;
          for(int j=1; j<=M; j++)
        if( A[i][j]==minim && B[i][j] == minim ) { out<<A[i][j]<<' ' << i<<' '<< j; ok=!ok; break; }
        if( ok ) break ;
      }


    return 0;
}