Cod sursa(job #1900878)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 3 martie 2017 17:11:31
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include<bits/stdc++.h>
#define maxN 105
using namespace std;
deque<pair<int,int> > q;
int rx,ry,jx,jy,a[maxN][maxN],Romeo[maxN][maxN],Julieta[maxN][maxN],n,m,isol,jsol;
int d[100][5];
char s[105];
void Initializare()
{
    d[1][1]=-1;
    d[1][2]=-1;
    d[2][1]=-1;
    d[2][2]=0;
    d[3][1]=-1;
    d[3][2]=1;
    d[4][1]=0;
    d[4][2]=-1;
    d[5][1]=0;
    d[5][2]=1;
    d[6][1]=1;
    d[6][2]=-1;
    d[7][1]=1;
    d[7][2]=0;
    d[8][1]=1;
    d[8][2]=1;
}
void Lee1()
{
    int n1,n2,nr1,nr2;
    q.clear();
    q.push_front({rx,ry});
    while(!q.empty())
    {
        n1=q.front().first;
        n2=q.front().second;
        for(int i=1;i<=8;i++)
        {
            nr1=n1+d[i][1];
            nr2=n2+d[i][2];
            if(!a[nr1][nr2])
            {
                if( (Romeo[nr1][nr2]>(1+Romeo[n1][n2])))
                {
                    Romeo[nr1][nr2]=1+Romeo[n1][n2];
                    q.push_back({nr1,nr2});
                }
            }
        }
        q.pop_front();
    }
}
void Lee2()
{
    int n1,n2,nr1,nr2;
    q.clear();
    q.push_front({jx,jy});
    while(!q.empty())
    {
        n1=q.front().first;
        n2=q.front().second;
        for(int i=1;i<=8;i++)
        {
            nr1=n1+d[i][1];
            nr2=n2+d[i][2];
            if(!a[nr1][nr2])
            {
                if((Julieta[nr1][nr2]>(1+Julieta[n1][n2])))
                {
                    Julieta[nr1][nr2]=(1+Julieta[n1][n2]);
                    q.push_back({nr1,nr2});
                }
            }
        }
        q.pop_front();
    }
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    scanf("%d%d",&n,&m);
    Initializare();
    for(int i=0;i<=(m+1);i++)
    {
        a[0][i]=a[n+1][i]=-1;
    }
    for(int i=0;i<=(n+1);i++)
    {
        a[i][0]=a[i][m+1]=-1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            Romeo[i][j]=Julieta[i][j]=100000;
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("\n");
        fread(s,1,m,stdin);
        for(int j=0;j<m;j++)
        {
            if(s[j]=='R')
            {
                rx=i;
                ry=j+1;
            }
                else
            if(s[j]=='J')
            {
                jx=i;
                jy=j+1;
            }
                else
            if(s[j]=='X')
            {
                a[i][j+1]=-1;
            }
                else
            if(s[j]==' ') a[i][j+1]=0;
        }
    }
    Romeo[rx][ry]=1;
    Julieta[jx][jy]=1;
    Lee1();
    Lee2();
    int minim=10000;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(Romeo[i][j]==Julieta[i][j])
        {
            if(Julieta[i][j]<minim)
            {
                minim=Julieta[i][j];
                isol=i;
                jsol=j;
            }
        }
    printf("%d %d %d\n",minim,isol,jsol);
    return 0;
}