Cod sursa(job #548066)

Utilizator laurionLaurentiu Ion laurion Data 7 martie 2011 04:25:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.04 kb
#include<fstream>
using namespace std;
#include<queue>
#include<cstring>
#include<iostream>
const int   dx[]={0,1,1, 1, 0,-1,-1,-1},
            dy[]={1,1,0,-1,-1,-1, 0, 1};
 /*
 bool a[120][120]={0};
 int D2[120][120];
 int D1[120][120];
    int n,m;
 pair<int,int> startJ,startR;

inline void julieta()
{

    queue<pair<int,int> >Q;
    pair<int,int> now,now2;

    memset(D1,0x3f,sizeof(D1));

    Q.push(startJ);
    D1[startJ.first][startJ.second]=1;
    int i;
    while(Q.empty()==false)
    {
        now=Q.front();
        Q.pop();
       // if(now==startR)
         //   return D1[now.first][now.second];
        for( i=0;i<8;++i)
        {
            now2=make_pair(now.first+dx[i],now.second+dy[i]);
            if(now2.first>=0 && now2.first<n && now2.second>=0 && now2.second
               && a[now2.first][now2.second]==false
               && D1[now2.first][now2.second]>D1[now.first][now.second]+1)
               {
                   D1[now2.first][now2.second]=D1[now.first][now.second]+1;
                   Q.push(now2);
               }
        }
    }
    //return -1;
}
inline void romeo()
{

    queue<pair<int,int> >Q;
    pair<int,int> now,now2;

    memset(D2,0x3f,sizeof(D2));

    Q.push(startR);
    D2[startR.first][startR.second]=1;
    int i;
    while(Q.empty()==false)
    {
        now=Q.front();
        Q.pop();
       // if(now==startJ)
         //   return D2[now.first][now.second];
        for( i=0;i<8;++i)
        {
            now2=make_pair(now.first+dx[i],now.second+dy[i]);
            if(now2.first>=0 && now2.first<n && now2.second>=0 && now2.second
               && a[now2.first][now2.second]==false
               && D2[now2.first][now2.second]>D2[now.first][now.second]+1)
               {
                   D2[now2.first][now2.second]=D2[now.first][now.second]+1;
                   Q.push(now2);
               }
        }
    }
    //return -1;
}
*/
int main()
{
    std::ifstream fin("rj.in");
    std::ofstream fout("rj.out");


    int i,j;
    char s[120];


    bool a[120][120]={0};
 int D2[120][120];
 int D1[120][120];
    int n,m;
 pair<int,int> startJ,startR;


    fin>>n>>m;

    fin.get();
    for(i=0;i<n;++i)
    {
        fin.getline(s,120);
        for(j=0;j<m;++j)
        {
            if(s[j]=='X')
                a[i][j]=true;
            else if(s[j]=='J')
            {
                startJ=make_pair(i,j);
            }
            else if(s[j]=='R')
            {
                startR=make_pair(i,j);
            }
        }

    }

    //julieta();
    //romeo();
    queue<pair<int,int> >Q;
    pair<int,int> now,now2;

    memset(D1,0x3f,sizeof(D1));

    Q.push(startJ);
    D1[startJ.first][startJ.second]=1;

    while(Q.empty()==false)
    {
        now=Q.front();
        Q.pop();
       // if(now==startR)
         //   return D1[now.first][now.second];
        for( i=0;i<8;++i)
        {
            now2=make_pair(now.first+dx[i],now.second+dy[i]);
            if(now2.first>=0 && now2.first<n && now2.second>=0 && now2.second
               && a[now2.first][now2.second]==false
               && D1[now2.first][now2.second]>D1[now.first][now.second]+1)
               {
                   D1[now2.first][now2.second]=D1[now.first][now.second]+1;
                   Q.push(now2);
               }
        }
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(D1[i][j]==0x3f3f3f3f)
                    cout<<"x ";
                else
                    cout<<D1[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
    }
     memset(D2,0x3f,sizeof(D2));

    Q.push(startR);
    D2[startR.first][startR.second]=1;

    while(Q.empty()==false)
    {
        now=Q.front();
        Q.pop();
       // if(now==startJ)
         //   return D2[now.first][now.second];
        for( i=0;i<8;++i)
        {
            now2=make_pair(now.first+dx[i],now.second+dy[i]);
            if(now2.first>=0 && now2.first<n && now2.second>=0 && now2.second
               && a[now2.first][now2.second]==false
               && D2[now2.first][now2.second]>D2[now.first][now.second]+1)
               {
                   D2[now2.first][now2.second]=D2[now.first][now.second]+1;
                   Q.push(now2);
               }

        }
            for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(D2[i][j]==0x3f3f3f3f)
                    cout<<"x ";
                else
                    cout<<D2[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
    }
    int min=0x3f3f3f3f+1,ii,jj;

    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            if(D1[i][j]<100000 && D1[i][j]==D2[i][j] )
            {
                if(D1[i][j]<min)
                {
                    ii=i;
                    jj=j;
                    min=D1[i][j];
                }
                else if(D1[i][j]==min && (i<ii || j<jj))
                {
                    ii=i;
                    jj=j;
                }
            }
        }
    }

    fout<<min<<' '<<ii+1<<' '<<jj+1<<'\n';
    return 0;
}