Cod sursa(job #1451375)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 16 iunie 2015 21:38:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <fstream>

using namespace std;

int n,m,a[105][105],i,jj,lr,cr,lj,cj,r[105][105],j[105][105],minim=100000000,linie,coloana;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

struct coord
{
    int lin,col;
};
coord q[50000];

inline void LeeRomeo()
{
    int pr,ul,x,y,xf,yf,k,val;
    pr=ul=1;
    q[1].lin=lr;
    q[1].col=cr;
    r[lr][cr]=1;
    while(pr<=ul)
    {
        x=q[pr].lin;
        y=q[pr].col;
        pr++;val=r[x][y];
        for(k=0;k<8;k++)
        {
            xf=x+dx[k];
            yf=y+dy[k];
            if(a[xf][yf]==1)
                if(r[xf][yf]==0 || r[xf][yf]>val+1)
                {
                    r[xf][yf]=val+1;
                    ul++;
                    q[ul].lin=xf;
                    q[ul].col=yf;
                }
        }
    }
}

inline void LeeJulieta()
{
    int pr,ul,x,y,xf,yf,k,val;
    pr=ul=1;
    q[1].lin=lj;
    q[1].col=cj;
    j[lj][cj]=1;
    while(pr<=ul)
    {
        x=q[pr].lin;
        y=q[pr].col;
        pr++;val=j[x][y];
        for(k=0;k<8;k++)
        {
            xf=x+dx[k];
            yf=y+dy[k];
            if(a[xf][yf]==1)
                if(j[xf][yf]==0 || j[xf][yf]>val+1)
                {
                    j[xf][yf]=val+1;
                    ul++;
                    q[ul].lin=xf;
                    q[ul].col=yf;
                }
        }
    }
}

inline void Solve()
{
    for(i=1;i<=n;i++)
        for(jj=1;jj<=m;jj++)
            if(r[i][jj]==j[i][jj] && r[i][jj]!=0 && r[i][jj]<minim)
            {
                minim=r[i][jj];
                linie=i;
                coloana=jj;
            }
}

int main()
{
    char c[210],caracter;
    ifstream fin ("rj.in");
    ofstream fout ("rj.out");
    fin>>n>>m;fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(c, 200);
        for(jj=0;jj<m;jj++)
        {
            caracter=c[jj];
            if(caracter=='R')
            {
                lr=i;
                cr=jj+1;
            }
            else
                if(caracter=='J')
                {
                    lj=i;
                    cj=jj+1;
                }
                else
                    if(caracter==' ')
                        a[i][jj+1]=1;
                    else
                        a[i][jj+1]=0;
        }
    }
    LeeRomeo();
    LeeJulieta();
    /*for(i=1;i<=n;i++)
    {
        for(jj=1;jj<=m;jj++)
            fout<<r[i][jj]<<" ";
        fout<<"\n";
    }
    fout<<"\n";
    for(i=1;i<=n;i++)
    {
        for(jj=1;jj<=m;jj++)
            fout<<j[i][jj]<<" ";
        fout<<"\n";
    }
    fout<<"\n";*/
    Solve();
    fout<<minim<<" "<<linie<<" "<<coloana<<"\n";
    return 0;
}