Cod sursa(job #2128182)

Utilizator SahMatCodrea Andrei SahMat Data 11 februarie 2018 15:22:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream fi("rj.in");
ofstream fo("rj.out");

char Map[101];
int a[101][101],drum[101*101][3];
int di[8]={0,-1,-1,-1,0,1,1,1},dj[8]={1,1,0,-1,-1,-1,0,1};
int n,m,i,j,x,y,rx,ry,jx,jy,k;
queue <pair<int,int> > q;

void Lee()
{
    int i2,j2;
    q.push(make_pair(rx,ry));

    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(int d=0;d<=7;d++)
        {
            i2=di[d]+i;
            j2=dj[d]+j;

            if(i2>=1 and i2<=n and j2>=1 and j2<=m and a[i2][j2]==0)
            {
                a[i2][j2]=a[i][j]+1;
                if(i==rx and j==ry)
                    a[i2][j2]+=2;
                q.push(make_pair(i2,j2));
            }
        }
    }

}

void cautare()
{
    int i2,j2;
    drum[++k][1]=jx;
    drum[k][2]=jy;
    i=jx;
    j=jy;
    while(a[i][j]!=1)
    {
         for(int d=0;d<=7;d++)
        {
            i2=di[d]+i;
            j2=dj[d]+j;

            if(i2>=1 and i2<=n and j2>=1 and j2<=m and a[i2][j2]==a[i][j]-1 )
            {
                drum[++k][1]=i2;
                drum[k][2]=j2;
                i=i2;
                j=j2;
                break;
            }
        }
    }
}

int main()
{
    fi>>n>>m;
    fi.getline(Map,101);
    for(i=1;i<=n;i++)
     {fi.getline(Map,101);
     for(j=0;j<m;j++)
     {
         if(Map[j]==' ')
         {
             a[i][j+1]=0;
         }

        if(Map[j]=='R')
        {
            rx=i;
            ry=j+1;
            a[i][j+1]=-2;
        }
        if(Map[j]=='J')
        {
            jx=i;
            jy=j+1;
             a[i][j+1]=0;
        }
        if(Map[j]=='X')
            a[i][j+1]=-1;

    }
     }


    Lee();
        /*for(i=1;i<=n;i++)
        {for(j=1;j<=m;j++)
        fo<<a[i][j];
        fo<<endl;
        }*/
    cautare();

    drum[++k][1]=rx;
    drum[k][2]=ry;
    /*for(i=1;i<=k;i++)
        fo<<drum[i][1]<<" "<<drum[i][2]<<endl;*/
    if(k%2==0)
    fo<<k/2<<" "<<drum[k/2][1]<<" "<<drum[k/2][2];
    else
      fo<<k/2+1<<" "<<drum[k/2+1][1]<<" "<<drum[k/2+1][2];

    return 0;
}