Cod sursa(job #1781585)

Utilizator qThunderStefan Durlanescu qThunder Data 16 octombrie 2016 23:52:47
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int dl[]={-1,0,1,0,-1,-1,1,1};
int dc[]={0,1,0,-1,-1,1,1,-1};
int i,j,l1,l2,c1,c2,lv,cv,l,c,n,m,p,u,a[102][102],b[102][102],minim,x,y;
struct coada
{
    int l;
    int c;
};
char cr[102];
coada que[10004];
int main()
{   fin>>n;
    fin>>m;
    minim=100002;
    for(i=1;i<=m+1;i++)
    {
        fin.getline(cr,100);
        for(j=0;j<m;j++)
        {
            if(cr[j]=='X')
                a[i-1][j+1]=b[i-1][j+1]=-1;
            if(cr[j]=='R')
            {
                l1=i-1;
                c1=j+1;
            }
            if(cr[j]=='J')
            {
                l2=i-1;
                c2=j+1;
            }
        }
    }
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=-1;
    for(j=0;j<=m+1;j++)
        a[0][j]=a[n+1][j]=-1;
    for(i=0;i<=n+1;i++)
        b[i][0]=b[i][m+1]=-1;
    for(j=0;j<=m+1;j++)
        b[0][j]=b[n+1][j]=-1;
    a[l1][c1]=1;
    que[1].l=l1;
    que[1].c=c1;
    p=u=1;
    while(p<=u)
    {
        l=que[p].l;
        c=que[p].c;
        p++;
        //8 vecini pt l,c
        for(i=0;i<=7;i++)
        {
            lv=l+dl[i];
            cv=c+dc[i];
            if(a[lv][cv]==0)
            {
                a[lv][cv]=a[l][c]+1;
                u++;
                que[u].l=lv;
                que[u].c=cv;
            }
        }
    }
    b[l2][c2]=1;
    que[1].l=l2;
    que[1].c=c2;
    p=u=1;
    while(p<=u)
    {
        l=que[p].l;
        c=que[p].c;
        p++;
        //4 vecini pt l,c
        for(i=0;i<=7;i++)
        {
            lv=l+dl[i];
            cv=c+dc[i];
            if(b[lv][cv]==0)
            {
                b[lv][cv]=b[l][c]+1;
                u++;
                que[u].l=lv;
                que[u].c=cv;
            }
        }
    }
    for(j=1;j<=m;j++)
    {
        for(i=1;i<=n;i++)
        {
            if(a[i][j]==b[i][j])
            {
                if(minim>a[i][j]&&a[i][j]>0)
                {
                    minim=a[i][j];
                    x=i;
                    y=j;
                }
            }
        }
    }
    fout<<minim<<" "<<x<<" "<<y;
    return 0;
}