Cod sursa(job #1436828)

Utilizator radu_cosmaRadu Cosma radu_cosma Data 16 mai 2015 15:02:07
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.83 kb
#include <stdio.h>
int a[101][101],b[101][101],r[101][101],k[101][101];
int n,m,xr,yr,xj,yj;
void read ()
{
    int i,j;
    char ch;
    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m+1; ++j)
        {
            scanf ("%c",&ch);
            if (ch=='\n' && j!=m+1)
            {
                ch=' ';
                ++j;
            }
            switch (ch)
            {
                case ' ':
                {
                    a[i][j]=0;
                    b[i][j]=0;
                    break;
                }
                case 'X':
                {
                    a[i][j]=-1;
                    b[i][j]=-1;
                    break;
                }
                case 'R':
                {
                    xr=i;
                    yr=j;
                    break;
                }
                case 'J':
                {
                    xj=i;
                    yj=j;
                    break;
                }
            }
        }
}
void solve ()
{
    int i,j,pas=0,gasit=1;
    r[xr][yr]=1;
    while (gasit)
    {
        gasit=0;
        ++pas;
        for (i=1; i<=n; ++i)
            for (j=1; j<=m; ++j)
                if (r[i][j]==pas)
                {
                    if (a[i-1][j]==0 && r[i-1][j]==0 && i-1<=n && i-1>=1)
                    {
                        gasit=1;
                        r[i-1][j]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i][j-1]==0 && r[i][j-1]==0 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        r[i][j-1]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i+1][j]==0 && r[i+1][j]==0 && i+1<=n && i+1>=1)
                    {
                        gasit=1;
                        r[i+1][j]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i][j+1]==0 && r[i][j+1]==0 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        r[i][j+1]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i-1][j-1]==0 && r[i-1][j-1]==0 && i-1<=n && i-1>=1 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        r[i-1][j-1]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i-1][j+1]==0 && r[i+1][j+1]==0 && i-1<=n && i-1>=1 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        r[i-1][j+1]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i+1][j-1]==0 && r[i+1][j-1]==0 && i+1<=n && i+1>=1 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        r[i+1][j-1]=pas+1;
                        a[i][j]=-1;
                    }
                    if (a[i+1][j+1]==0 && r[i+1][j+1]==0 && i+1<=n && i+1>=1 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        r[i+1][j+1]=pas+1;
                        a[i][j]=-1;
                    }
                }
    }
    gasit=1;
    pas=0;
    k[xj][yj]=1;
    while (gasit)
    {
        gasit=0;
        ++pas;
        for (i=1; i<=n; ++i)
            for (j=1; j<=m; ++j)
                if (k[i][j]==pas)
                {
                    if (b[i-1][j]==0 && k[i-1][j]==0 && i-1<=n && i-1>=1)
                    {
                        gasit=1;
                        k[i-1][j]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i][j-1]==0 && k[i][j-1]==0 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        k[i][j-1]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i+1][j]==0 && k[i+1][j]==0 && i+1<=n && i+1>=1)
                    {
                        gasit=1;
                        k[i+1][j]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i][j+1]==0 && k[i][j+1]==0 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        k[i][j+1]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i-1][j-1]==0 && k[i-1][j-1]==0 && i-1<=n && i-1>=1 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        k[i-1][j-1]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i-1][j+1]==0 && k[i-1][j+1]==0 && i-1<=n && i-1>=1 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        k[i-1][j+1]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i+1][j-1]==0 && k[i+1][j-1]==0 && i+1<=n && i+1>=1 && j-1<=m && j-1>=1)
                    {
                        gasit=1;
                        k[i+1][j-1]=pas+1;
                        b[i][j]=-1;
                    }
                    if (b[i+1][j+1]==0 && k[i+1][j+1]==0 && i+1<=n && i+1>=1 && j+1<=m && j+1>=1)
                    {
                        gasit=1;
                        k[i+1][j+1]=pas+1;
                        b[i][j]=-1;
                    }
                }

    }
    int imin=0,jmin=0,min=1000000000;
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            if (r[i][j]==k[i][j] && r[i][j] && r[i][j]<min)
            {
                imin=i;
                jmin=j;
                min=r[i][j];
            }
    printf ("%d %d %d",min,imin,jmin);

}
int main ()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    read ();
    solve ();
    return 0;
}