Cod sursa(job #992999)

Utilizator Eugen_VlasieFMI Vlasie Eugen Eugen_Vlasie Data 2 septembrie 2013 23:17:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <fstream>

using namespace std;
ofstream g("rj.out");
int n,m,i,j,pr,ul,x,y,al,ac,bl,bc,dl[9],dc[9],cl[20000],cc[20000],lr,t=20000,cr,lj,cj,a[110][110],v[110][110];
char c;
void verif(int s[110][110])
{
    int i,j;
    for(i=0;i<=n+1;i++)
    {
        for(j=0;j<=m+1;j++)
        {
            if(s[i][j]>-1&&s[i][j]<10)
                g<<" ";
            g<<s[i][j]<<" ";
        }
        g<<'\n';
    }
}
int main()
{
    FILE *f;
    f=fopen("rj.in","r");
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&m);
    fscanf(f,"%c",&c);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            //verif();
            //g<<'\n';
            fscanf(f,"%c",&c);

            if(c=='X')
                v[i][j]=-1;
            else
                if(c=='R')
                {
                    lr=i;
                    cr=j;
                }
                else
                    if(c=='J')
                    {
                        lj=i;
                        cj=j;
                    }
        }
        fscanf(f,"%c",&c);
    }
    for(i=0;i<=n+1;i++)
    {
        v[i][0]=-1;
        v[i][m+1]=-1;
    }
    for(i=0;i<=m+1;i++)
    {
        v[0][i]=-1;
        v[n+1][i]=-1;
    }
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++)
            a[i][j]=v[i][j];
    dl[1]=-1;
    dl[2]=-1;
    dl[3]=0;
    dl[4]=1;
    dl[5]=1;
    dl[6]=1;
    dl[7]=0;
    dl[8]=-1;
    dc[1]=0;
    dc[2]=1;
    dc[3]=1;
    dc[4]=1;
    dc[5]=0;
    dc[6]=-1;
    dc[7]=-1;
    dc[8]=-1;

    //verif(v);
    //g<<'\n';
    pr=ul=0;
    a[lj][cj]=1;
    cl[0]=lj;
    cc[0]=cj;
    while(pr<=ul)
    {
        al=cl[pr];
        ac=cc[pr];
        pr++;
        for(i=1;i<=8;i++)
        {
            bl=al+dl[i];
            bc=ac+dc[i];
            if(a[bl][bc]==0)
            {
                a[bl][bc]=a[al][ac]+1;
                ul++;
                cl[ul]=bl;
                cc[ul]=bc;

            }
        }
    }
    pr=ul=0;
    v[lr][cr]=1;
    cl[0]=lr;
    cc[0]=cr;
    while(pr<=ul)
    {
        al=cl[pr];
        ac=cc[pr];
        pr++;
        for(i=1;i<=8;i++)
        {
            bl=al+dl[i];
            bc=ac+dc[i];
            if(v[bl][bc]==0)
            {
                v[bl][bc]=v[al][ac]+1;
                ul++;
                cl[ul]=bl;
                cc[ul]=bc;
            }
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==v[i][j]&&a[i][j]>0)
            {
                if(t>a[i][j])
                {
                    t=a[i][j];
                    x=i;
                    y=j;
                }
            }
        }
    g<<t<<" "<<x<<" "<<y<<'\n';
    //verif(a);
   // g<<'\n';
    return 0;
}