Cod sursa(job #832173)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 9 decembrie 2012 22:41:33
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<fstream>
struct sol {int lin;int col;};
using namespace std;
int a[110][110],b[110][110],d[110][110];
char ch[101];
int dl[]={-1,-1,-1,0,0,1,1,1};
int dc[]={0,1,-1,1,-1,+1,0,-1};
int main()
{
    int m,n,i,j;
    typedef sol Coada [110*110];
    Coada c;
    int inc=0,sf=-1;
    sol ppr,ppj,p,v;
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        a[i][0]=a[i][m+1]=-1;
        b[i][0]=b[i][m+1]=-1;
        d[i][0]=d[i][m+1]=-1;
        fin.get();
        fin.get(ch,m+1,'\n');
        for(j=0;j<m && ch[j];j++)
            if(ch[j]=='X')
             {
                 a[i][j+1]=-1;
                 b[i][j+1]=-1;
                 d[i][j+1]=-1;
             }
                else
                if(ch[j]=='R')
                {
                    ppr.lin=i;
                    ppr.col=j+1;
                }
                else
                {
                    if(ch[j]=='J')
                    {
                        ppj.lin=i;
                        ppj.col=j+1;
                    }
                }
    }
    for(i=0;i<=m+1;i++)
    {
        a[0][i]=a[n+1][i]=-1;
        b[0][i]=b[n+1][i]=-1;
        d[0][i]=d[n+1][i]=-1;
    }
    a[0][0]=a[0][m+1]=a[n+1][0]=a[n+1][m+1]=-1;
    b[0][0]=b[0][m+1]=b[n+1][0]=b[n+1][m+1]=-1;
    d[0][0]=d[0][m+1]=d[n+1][0]=d[n+1][m+1]=-1;
    b[ppr.lin][ppr.col]=1;
   // printf("%d %d\n",ppr.lin,ppr.col);
    c[++sf]=ppr;
    while(inc<=sf)
    {
        p=c[inc++];
        for(i=0;i<8;i++)
        {
            v.lin=p.lin+dl[i];
            v.col=p.col+dc[i];
            if(b[v.lin][v.col]==0)
            {
                b[v.lin][v.col]=b[p.lin][p.col]+1;
                c[++sf]=v;
            }
        }
    }
    d[ppj.lin][ppj.col]=1;
    sf=-1,inc=0;
    c[++sf]=ppj;
    while(inc<=sf)
    {
        p=c[inc++];
        for(i=0;i<8;i++)
        {
            v.lin=p.lin+dl[i];
            v.col=p.col+dc[i];
            if(d[v.lin][v.col]==0)
            {
                d[v.lin][v.col]=d[p.lin][p.col]+1;
                c[++sf]=v;
            }
        }
    }
    int MIN=9999999;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            if(b[i][j]==d[i][j]&&b[i][j]>1&&b[i][j]<MIN)
            {
                MIN=b[i][j];
                ppj.lin=i;
                ppj.col=j;
            }
    }
    fout<<MIN<<" "<<ppj.lin<<" "<<ppj.col<<"\n";
    return 0;
}