Cod sursa(job #2029352)

Utilizator trettdragosTrett Dragos trettdragos Data 29 septembrie 2017 21:19:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int n, m, a[177][177], ri, rj, ji, jj, juliet[177][177];
int pi, pj, pif, pjf;

int di[8]= {-1, 0, 0, 1, -1, -1, 1, 1};
int dj[8]= {0, -1, 1, 0, -1, 1, -1, 1};
queue< pair <int, int> >Q;


void Citire ()
{
    freopen ("rj.in","r",stdin);
    scanf ("%d %d\n", &n, &m);
    char loc;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            scanf ("%c",&loc);
            if (loc=='\n')
                scanf ("%c",&loc);
            if (loc=='X')
                a[i][j]=-1;
            else if (loc=='R')
            {
                ri=i;
                rj=j;

            }
            else if (loc=='J')
            {
                ji=i;
                jj=j;
            }
            else if(loc=='v'){
                a[i][j]=0;
            }
        }
}


int Lee (int a[177][177], int pi, int pj)
{
    Q.push (make_pair(pi,pj));
    a[pi][pj]=1;
    while (!Q.empty())
    {
        int ic=Q.front().first;
        int jc=Q.front().second;
        Q.pop();
        for (int i=0; i<8; i++)
        {
            int iv=ic+di[i];
            int jv=jc+dj[i];
            if (a[iv][jv]==0)
            {
                a[iv][jv]=1+a[ic][jc];
                if (iv==pif && jv==pjf)
                    return a[iv][jv]-1;
                Q.push(make_pair(iv,jv));
            }
        }
    }
    return -1;
}


void Bordare ()
{
    for (int j=0; j<=m+1; j++)
    {
        a[0][j]=-1;
        a[n+1][j]=-1;
    }
    for (int i=0; i<=n+1; i++)
    {
        a[i][0]=-1;
        a[i][m+1]=-1;
    }
}


int main()
{
    freopen ("rj.out","w",stdout);
    Citire();
    Bordare();
    for (int i=0; i<=n+1; i++)
        for (int k=0; k<=m+1; k++)
            juliet[i][k]=a[i][k];
    Lee(a,ri,rj);
    Lee(juliet,ji,jj);
    int ok=1;
    for (int i=1; i<=n && ok==1; i++)
    {
        for (int k=1; k<=m && ok==1; k++)
            if (juliet[i][k]==a[i][k] && juliet[i][k]>0)
            {
                cout<<a[i][k]<<" "<<i<<" "<<k;
                ok=0;
            }
    }
    return 0;
}