Cod sursa(job #1579923)

Utilizator andreiskiorAndrei Cristian Nastase andreiskior Data 25 ianuarie 2016 11:20:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
// AUTOR SURSA : Alexia Ichim (ialexia_ioana)

#include <cstdio>

char a[101];
int b[101][101];
int r[101][101];
int jl[101][101];
int dl[]= {-1,-1,0,1,1,1,0,-1};
int dc[]= {0,1,1,1,0,-1,-1,-1};
int xr, yr, xj, yj, n, m;

struct coord
{
    int lin, col;
};
coord Q[10005];

void bordare(int b[101][101])
{
    int i, j;
    for(i=0; i<=n+1; i++)
    {
        b[i][0]=-1;
        b[i][m+1]=-1;
    }
    for(j=0; j<=m+1; j++)
    {
        b[0][j]=-1;
        b[n+1][j]=-1;
    }

}

void lee_romeo()
{
    int ultim=0, prim=1, i;
    coord ps, p, v;
    ps.lin=xr;
    ps.col=yr;
    Q[++ultim]=ps;
    r[ps.lin][ps.col]=1;
    while(prim<=ultim)
    {
        p=Q[prim];
        prim++;
        for(i=0; i<8; i++)
        {
            v.lin=p.lin+dl[i];
            v.col=p.col+dc[i];
            if(r[v.lin][v.col]==0 && b[v.lin][v.col]!=-1)
            {
                ultim++;
                Q[ultim]=v;
                r[v.lin][v.col]=r[p.lin][p.col]+1;
            }
        }
    }
}
void lee_julieta()
{
    int ultim=0, prim=1, i;
    coord ps, p, v;
    ps.lin=xj;
    ps.col=yj;
    Q[++ultim]=ps;
    jl[ps.lin][ps.col]=1;
    while(prim<=ultim)
    {
        p=Q[prim];
        prim++;
        for(i=0; i<8; i++)
        {
            v.lin=p.lin+dl[i];
            v.col=p.col+dc[i];
            if(jl[v.lin][v.col]==0 && b[v.lin][v.col]!=-1)
            {
                ultim++;
                Q[ultim]=v;
                jl[v.lin][v.col]=jl[p.lin][p.col]+1;
            }
        }
    }
}

using namespace std;

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    int pozx, pozy, t, i, j, nr;
    scanf("%d%d\n", &n, &m);
    for(i=1; i<=n; i++)
    {
        j=1;
        scanf("%c", &a[j]);
        while(a[j]!='\n')
        {
            j++;
            scanf("%c", &a[j]);
        }
        for(j=1; j<=m; j++)
        {
            if (a[j]=='X')
                b[i][j]=-1;
            if (a[j]=='J')
            {
                xj=i;
                yj=j;
                b[xj][yj]=0;
            }
            if (a[j]=='R')
            {
                xr=i;
                yr=j;
                b[xr][yr]=0;
            }
        }
    }
    bordare(b);
    bordare(jl);
    bordare(r);
    lee_julieta();
    lee_romeo();
    t=100000;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(r[i][j]==jl[i][j] && t>r[i][j] && b[i][j]!=-1 && r[i][j]!=0)
            {
                nr=r[i][j];
                t=r[i][j];
                pozx=i;
                pozy=j;
            }
        }
    }
    printf("%d %d %d\n", t, pozx, pozy);
    return 0;
}