Cod sursa(job #97147)

Utilizator raduzerRadu Zernoveanu raduzer Data 5 noiembrie 2007 16:09:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>

const int dx[4]= {1, 0 , -1 , 0};
const int dy[4]= {0, 1 , 0 , -1};

int a[10010][2],b[110][110],d[110][110],n,m,rl,rc,jl,jc,z,t,pl,pc;
char c[110][110];

int main()
{
    freopen("rj.in","rt",stdin);
    freopen("rj.out","wt",stdout);
    scanf("%hd %hd\n",&n,&m);
    int i,j;
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=m; ++j)
        {
            scanf("%c",&c[i][j]);
            if (c[i][j]=='R')
            {
                 rl=i;
                 rc=j;
            }
            if (c[i][j]=='J')
            {
                 jl=i;
                 jc=j;
            }
        }
		scanf("\n");
    }
    int x,y;
    z=1;
    a[1][0]=rl;
    a[1][1]=rc;
    b[rl][rc]=0 ;
    for (i=1; i<=z; ++i)
    {
        for (j=0; j<4; ++j)
        {
            x=a[i][0]+dx[j];
            y=a[i][1]+dy[j];
            if (x>0 && x<=n && y>0 && y<=m && c[x][y]!='X' && b[x][y]==0 && (x!=rl || y!=rc))
            {
                    b[x][y]=b[a[i][0]][a[i][1]]+1;
                    ++z;
                    a[z][0]=x;
                    a[z][1]=y;
            }
        }
		a[i][0]=0;
		a[i][1]=0;
    }
    


    t=0x3f3f3f3f;
    z=1;
    a[1][0]=jl;
    a[1][1]=jc;
    d[jl][jc]=0;

    for (i=1; i<=z; ++i)
    {
        for (j=0; j<4; ++j)
        {
            x=a[i][0]+dx[j];
            y=a[i][1]+dy[j];
            if (x>0 && x<=n && y>0 && y<=m && c[x][y]!='X' && d[x][y]==0 && (x!=jl || y!=jc))
            {
                    d[x][y]=d[a[i][0]][a[i][1]]+1;
                    if (d[x][y]==b[x][y] && d[x][y]<t) 
                    {
                         t=d[x][y];
                         pl=x;
                         pc=y;
                    }
					++z;
					a[z][0]=x;
					a[z][1]=y;
            }
        }
    }


    printf("%d %d %d",t,pl,pc);
    return 0;
}