Cod sursa(job #330033)

Utilizator freak93Adrian Budau freak93 Data 8 iulie 2009 14:48:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<cstdio>
#include<cstring>
#define maxn 105

char b[maxn][maxn];

int a[maxn][maxn],i,j,n,m,k,xr,yr,xj,yj,x,y,c[maxn][maxn];

int coada[maxn*maxn][2],p,q,dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};

int mod(int a)
{
    if(a<0)
        return -a;
    return a;
}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    scanf("%d %d\n",&n,&m);

    for(i=1;i<=n;++i)
    {
        fgets(b[i],sizeof(b[i]),stdin);
        for(j=0;j<m;++j)
            if(b[i][j]=='X')
                a[i][j+1]=-1;
            else
            {
                a[i][j+1]=0;
                if(b[i][j]=='R')
                    xr=i,yr=j+1;
                else
                    if(b[i][j]=='J')
                        xj=i,yj=j+1;
            }
    }

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

    for(i=0;i<=n+1;++i)
        for(j=0;j<=m+1;++j)
            c[i][j]=a[i][j];

    coada[++p][0]=xr;
    coada[p][1]=yr;
    q=1;

    while(p<=q)
    {
        x=coada[p][0];
        y=coada[p][1];
        ++p;
        for(i=0;i<8;++i)
            if(a[x+dx[i]][y+dy[i]]==0)
                a[x+dx[i]][y+dy[i]]=a[x][y]+1,coada[++q][0]=x+dx[i],coada[q][1]=y+dy[i];
    }

    p=0;

    coada[++p][0]=xj;
    coada[p][1]=yj;
    q=1;

    while(p<=q)
    {
        x=coada[p][0];
        y=coada[p][1];
        ++p;
        for(i=0;i<8;++i)
            if(c[x+dx[i]][y+dy[i]]==0)
                c[x+dx[i]][y+dy[i]]=c[x][y]+1,coada[++q][0]=x+dx[i],coada[q][1]=y+dy[i];
    }

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(mod(a[i][j]-c[i][j])<=1&&a[i][j]+c[i][j]==a[xj][yj])
            {
                printf("%d %d %d",i,j,a[xj][yj]);
                fclose(stdin);
                fclose(stdout);
                return 0;
            }
    fclose(stdin);
    fclose(stdout);
    return 0;
}