Cod sursa(job #1065791)

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

queue < pair <int,int> > q;

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

void lee(int a[maxn][maxn],int xi,int yi){
     int x,y;
     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(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=0;i<=n+1;i++){ a[i][0]=-1; a[i][m+1]=-1; }
    for(j=0;j<=m+1;j++){ a[0][j]=-1; a[n+1][j]=-1; }
                     
    for(i=0;i<=n+1;i++)
      for(j=0;j<=m+1;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;
}