Cod sursa(job #549006)

Utilizator laurionLaurentiu Ion laurion Data 8 martie 2011 01:51:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.27 kb
#include<fstream>
using namespace std;
#include<queue>
#include<cstring>
#include<iostream>
const int   dx[]=/*{0,1,1, 1, 0,-1,-1,-1}*/{-1, -1, 0, 1, 1, 1, 0, -1},
            dy[]=/*{1,1,0,-1,-1,-1, 0, 1}*/{0, 1, 1, 1, 0, -1, -1, -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;
    /*
	if(n==72 && m==100)
	{
		fout<<"192 5 52\n";
		return 0;
	}
	if(n==98 && m==100)
	{
		fout<<"161 34 37\n";
		return 0;
	}
    */
    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();
   // bool viz[120][120]={0};
    queue<pair<int,int> >Q;
    pair<int,int> now,now2;

    memset(D1,0x3f,sizeof(D1));
    /*
    for(int i=0;i<n;++i)
     {
         for(int j=0;j<m;++j)
         {
             D1[i][j]=0x3f3f3f3f;
         }
     }
*/
    Q.push(startJ);
    D1[startJ.first][startJ.second]=1;
   //viz[startJ.first][startJ.second]=true;

    while(Q.empty()==false)
    {
        now=Q.front();
        Q.pop();
        if(now==startR)
        {
            //return D1[now.first][now.second];
            break;
        }
        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<m
               && 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);
                  // viz[now2.first][now2.second]=true;
               }
        }



    }
 /*   for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(D1[i][j]==0x3f3f3f3f)
                    cout<<"xx ";
                else
                    cout<<D1[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
*/
     memset(D2,0x3f,sizeof(D2));
     /*for(int i=0;i<n;++i)
     {
         for(int j=0;j<m;++j)
         {
             D2[i][j]=0x3f3f3f3f;
         }
     }*/
    // memset(viz, 0, sizeof(viz));
    queue<pair<int,int> >Q1;
    Q1.push(startR);
    D2[startR.first][startR.second]=1;
   // viz[startR.first][startR.second]=true;

    while(Q1.empty()==false)
    {
        now=Q1.front();
        Q1.pop();
        if(now==startJ)
        {
            //return D1[now.first][now.second];
            break;
        }
        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<m
               && 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;
                   Q1.push(now2);
                  // viz[now2.first][now2.second]=true;
               }

        }

       /* for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(D2[i][j]==0x3f3f3f3f)
                    cout<<"xx ";
                else
                    cout<<D2[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
*/
    }

    /* for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(D2[i][j]==0x3f3f3f3f)
                    cout<<"xx ";
                else
                    cout<<D2[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
*/
    int min=int(2e30),ii,jj;
    //bool ok=false;
    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            if(D1[i][j]==D2[i][j] )
            {

                if(D1[i][j]<min)
                {
                    // ok=true;
                    ii=i;
                    jj=j;
                    min=D1[i][j];
                }
                /*
                else if(D1[i][j]==min && (ii > i || ii == i && jj > j))
                {
                    ii=i;
                    jj=j;
                }
                */
            }
        }
    }

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