Cod sursa(job #1561700)

Utilizator titusTitus A titus Data 4 ianuarie 2016 14:01:25
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <cstdio>
using namespace std;

int dx[]={0 ,0 ,1 ,-1, 1, 1, -1, -1};
int dy[]={1 ,-1 ,0, 0, 1, -1, 1, -1};
char c1;
int Min,tmin,p1,p2,i,j,xr,yr,xj,yj,m,n,u,s,p,tr[101][101],tj[101][101];
bool r[101][101],j2[101][101];
struct elem
{
    int l,c;
}c[10001],d[10001],x,z;
void r1()
{
    p=1;
    c[1].l=xr;
    c[1].c=yr;
    tr[xr][yr]=1;
    u=1;
    while(p <= u)
    {
        z=c[p];
        ++p;
        for(int i=0;i<8;++i)
        {
            x.l=z.l+dx[i];
            x.c=z.c+dy[i];
            if((x.l>0&&x.c>0)&&(x.c<=m&&x.l<=n))
                if(r[x.l][x.c]==0&&(tr[x.l][x.c]>tr[z.l][z.c]+1))
                {
                    r[x.l][x.c]=1;
                    ++u;
                    c[u]=x;
                    tr[x.l][x.c]=tr[z.l][z.c]+1;
                }
        }
    }
}
void j1()
{
    p=1;
    c[1].l=xj;
    c[1].c=yj;
    tj[xj][yj]=1;
    u=1;
    while(p<=u)
    {
        z=c[p];
        ++p;
        for(int i=0;i<8;++i)
        {
            x.l=z.l+dx[i];
            x.c=z.c+dy[i];
            if((x.l>0&&x.c>0)&&(x.c<=m&&x.l<=n))
            {
                if(j2[x.l][x.c]==0&&(tj[x.l][x.c]>tj[z.l][z.c]+1))
                {
                    j2[x.l][x.c]=1;
                    ++u;
                    c[u]=x;
                    tj[x.l][x.c]=tj[z.l][z.c]+1;
                }
            }
        }
    }
}
int Max1(int x, int y)
{
    if(x>y) return x;
       else return y;
}
int main ()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1;i<=n;++i)
    {
        scanf("%c", &c1);
        for(j=1;j<=m;++j)
        {
            scanf("%c", &c1);
            if(c1=='R')
            {
                xr=i;
                yr=j;
            }
            else if(c1=='J')
            {
                xj=i;
                yj=j;
            }
            else if(c1=='X')
            {
                r[i][j]=1;
                j2[i][j]=1;
            }
            tr[i][j]=100000;
            tj[i][j]=100000;
        }

    }
    r1();
    j1();
    tmin=100000;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
            {
                if(tr[i][j]==tj[i][j]&&(tr[i][j]!=100000&&tj[i][j]!=100000))
                {
                    if(tmin>tr[i][j])
                    {
                        tmin=tr[i][j];
                        p1=i;
                        p2=j;
                    }
//                    else if(tr[i][j]==tmin)
//                    {
//                        if(i<p1)
//                        {
//                            tmin=tr[i][j];
//                            p1=i;
//                            p2=j;
//                        }
//                        else if(j<p2&&i==p1)
//                        {
//                            tmin=tr[i][j];
//                            p1=i;
//                            p2=j;
//                        }
//                    }
                }
            }
    }
    printf("%d %d %d\n", tmin, p1, p2);
    return 0;
}