Cod sursa(job #93498)

Utilizator igorPirnau Igor igor Data 18 octombrie 2007 21:46:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream.h>

#define nmax 101

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[101][101],b[101][101],i,j,imin,jmin,min=32000;
int n,m,xr,yr,xj,yj;
char cr[101];

int bun(int a[][nmax],int x, int y)
{
    if(x <= 0 || x > n || y <= 0 || y > n) return 0;
    if(a[x][y] != 0) return 0;
    return 1;
}

void bfs(int a[][nmax],int x1,int y1)
{   int stx[nmax * nmax], sty[nmax * nmax], q;    
    int p = q = 1;
    stx[1] = x1; sty[1] = y1;
    while(q <= p)
    {
        for(int i = 0; i < 8; i++)
             if( bun(a, stx[q] + vx[i], sty[q] + vy[i]))
             {   
                p++;
                stx[p] = stx[q] + vx[i];
                sty[p] = sty[q] + vy[i];
                a[stx[p]][sty[p]] = a[stx[q]][sty[q]] + 1;
             }
        q++;
    }
}

int main()
{   
    f>>n>>m;
    f.getline(cr,101);
    for(i=1;i<=n;i++)
        {   f.getline(cr,101);
            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=1;i<=n;i++)
        for(j=1;j<=m;j++) c[i][j]=b[i][j];

    bfs(b,xr,yr);
    bfs(c,xj,yj);
    
    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;
}