Cod sursa(job #93619)

Utilizator igorPirnau Igor igor Data 19 octombrie 2007 17:09:23
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<fstream.h>

#define nmax 102

ifstream f("rj.in");
ofstream g("rj.out");

int vx[]={0,0,1,1,-1,1,-1,-1}, vy[]={-1,1,1,0,-1,-1,0,1};
int c[102][102],b[102][102],i,j,imin,jmin,min=32000;
int n,m,xr,yr,xj,yj;
char cr[102];

int main()
{   
    f>>n>>m;
    f.getline(cr,102);
    for(i=1;i<=n;i++)
        {   f.getline(cr,102);
            for(j=0;j<m;j++)
            if(cr[j]==' ') b[i][j+1]=0;
              else if(cr[j]=='X') b[i][j+1]=-1;  
                     else if(cr[j]=='R')
                          {
                            xr=i;
                            yr=j+1;
                            b[i][j+1]=0;
                          }
                            else
                            {
                                xj=i;
                                yj=j+1;
                                b[i][j+1]=0;
                            }
        }
    f.close();

    for(i=0;i<=n+1;i++)
        {
            b[0][i]=-1;
            b[i][0]=-1;
            b[n+1][i]=-1;
            b[i][n+1]=-1;
        }
    
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) c[i][j]=b[i][j];

    int stx[nmax * nmax], sty[nmax * nmax], q;    
    int p = q = 1;
    stx[1] = xr; sty[1] = yr;
    while(q <= p)
    {
        for(int i = 0; i < 8; i++)
             if(! b[ stx[q] + vx[i] ][ sty[q] + vy[i] ])
             {   
                p++;
                stx[p] = stx[q] + vx[i];
                sty[p] = sty[q] + vy[i];
                b[stx[p]][sty[p]] = b[stx[q]][sty[q]] + 1;
             }
        q++;
    }

    stx[1] = xj; sty[1] = yj;
    p = q = 1;
    while(q <= p)
    {
        for(int i = 0; i < 8; i++)
             if(! c[ stx[q] + vx[i] ][ sty[q] + vy[i] ])
             {   
                p++;
                stx[p] = stx[q] + vx[i];
                sty[p] = sty[q] + vy[i];
                c[stx[p]][sty[p]] = b[stx[q]][sty[q]] + 1;
             }
        q++;
    }
    
    
    for(i=1;i<=n;i++)
       for(j=1;j<=m;j++) if(b[i][j]>0) if(b[i][j]==c[i][j]) if(b[i][j]<min){ min=b[i][j];
                                                                             imin=i;
                                                                             jmin=j;
                                                                           }
    
    g<<min+1<<' '<<imin<<' '<<jmin;
    g.close();
    return 0;
}