Cod sursa(job #966577)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 26 iunie 2013 11:50:07
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int q[2][10000],i,j,n,m,a[103][103],b[103][103],min1=10000,xf,yf,xj,yj;
char c;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

void leer()
{
    int st,dr,x,y,xx,yy;

    st=0;
    dr=0;
    while(st<=dr)
    {
        x=q[0][st];
        y=q[1][st];
        for(i=0;i<8;i++)
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(a[xx][yy]==0||a[xx][yy]>a[x][y]+1)
            {
                a[xx][yy]=a[x][y]+1;
                dr++;
                q[0][dr]=xx;
                q[1][dr]=yy;
            }
        }
        st++;
    }
}

void leej()
{
    int st,dr,x,y,xx,yy;

    st=0;
    dr=0;
    q[0][0]=xj;
    q[1][0]=yj;
    while(st<=dr)
    {
        x=q[0][st];
        y=q[1][st];
        for(i=0;i<8;i++)
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(b[xx][yy]==0||b[xx][yy]>b[x][y]+1)
            {
                b[xx][yy]=b[x][y]+1;
                dr++;
                q[0][dr]=xx;
                q[1][dr]=yy;
            }
        }
        st++;
    }
}



int main ()
{
    f>>n>>m;
    f.get();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
    {
        f.get(c);
        if(c=='X') a[i][j]=-1,b[i][j]=-1;
        else if(c=='R') a[i][j]=b[i][j]=1,q[0][0]=i,q[1][0]=j;
        else if(c=='J') a[i][j]=b[i][j]=1,xj=i,yj=j;
        else if(c==' ') a[i][j]=b[i][j]=0;
    }
    f.get();
    }

    for(i=0;i<=n+1;i++) a[i][0]=b[i][0]=a[i][m+1]=b[i][m+1]-1;
    for(i=0;i<=m+1;i++) a[0][i]=a[n+1][i]=b[0][i]=b[n+1][i]=-1;

    leer();
    leej();

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        if(a[i][j]==b[i][j]&&min1>a[i][j]&&a[i][j]!=-1&&a[i][j]!=1) min1=a[i][j],xf=i,yf=j;
    }
    g<<min1<<" "<<xf<<" "<<yf;
}