Cod sursa(job #1065848)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 23 decembrie 2013 19:04:58
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<fstream>
#include<string>
#include<queue>
#define maxn 105
using namespace std;
ifstream fi("rj.in");
ofstream fo("rj.out");

queue < pair <short int,short int> > q;

int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],sol=maxn*maxn;
short int dx[]={-1,-1,-1,0,0,1,1,1};
short int dy[]={-1,0,1,-1,1,-1,0,1};
short int i,j,n,m,k=0;
short int xa[4],ya[4];
string s;

bool este(short int a,short int b){
     return (a>=1 && a<=n && b>=1 && b<=m);
}

void lee(int a[maxn][maxn],short int xi,short int yi){
     short int x,y;
     short int i;
     
     a[xi][yi]=1;
     q.push(make_pair(xi,yi));
     
     while(q.size())
     {
      x=q.front().first;
      y=q.front().second;
      
      for(i=0;i<9;i++)
        if(este(x+dx[i],y+dy[i]) && a[x+dx[i]][y+dy[i]]==0)
          {
           a[x+dx[i]][y+dy[i]]=a[x][y]+1;
           q.push(make_pair(x+dx[i],y+dy[i]));
          }
      q.pop();               
     }
}

int main(){
    fi>>n>>m;
    getline(fi,s);
    
    for(i=1;i<=n;i++){
                      getline(fi,s); 
                      for(j=0;j<m;j++)
                        if(s[j]==' ') a[i][j+1]=0;
                        else if(s[j]=='X') a[i][j+1]=-1;
                        else if(s[j]=='R' || s[j]=='J'){
                                                        a[i][j+1]=0;
                                                        xa[++k]=i; 
                                                        ya[k]=j+1;
                                                       }
                     }
                                 
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++){
                          b[i][j]=a[i][j];
                          c[i][j]=a[i][j];
                         }                 
    
    lee(b,xa[1],ya[1]);
    lee(c,xa[2],ya[2]);
    
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        if(b[i][j]>0 && b[i][j]==c[i][j] && b[i][j]<sol){
                                                         sol=b[i][j];
                                                         xa[1]=i;
                                                         ya[1]=j;
                                                        } 
    
    fo<<sol<<" "<<xa[1]<<" "<<ya[1];

    fi.close();
    fo.close();
    return 0;
}