Cod sursa(job #1925537)

Utilizator maresioanMares Ioan maresioan Data 13 martie 2017 12:49:45
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <fstream>
#include <queue>
using namespace std;

int N , M ;

int A[120][120] ;

queue <int> C ;
queue <int> D ;

int functie(int p, int q,int **tmin)
{
    C.push(p);
    D.push(q);

    while(!C.empty())
    {
        p = C.front();
        C.pop();
        q = D.front();
        D.pop();
        if (p>1 && q>1 && (A[p-1][q-1]==32) && !tmin[p-1][q-1])
        {
            C.push(p-1);
            D.push(q-1);
            tmin[p-1][q-1]=tmin[p][q]+1;
        }
        if (p>1 && A[p-1][q]==32 && !tmin[p-1][q])
        {
            C.push(p-1);
            D.push(q);
            tmin[p-1][q]=tmin[p][q]+1;
        }
        if (p>1 && q<M && (A[p-1][q+1]==32) && !tmin[p-1][q+1])
        {
            C.push(p-1);
            D.push(q+1);
            tmin[p-1][q+1]=tmin[p][q]+1;
        }
        if (q>1 && (A[p][q-1]==32) && !tmin[p][q-1])
        {
            C.push(p);
            D.push(q-1);
            tmin[p][q-1]=tmin[p][q]+1;
        }
        if (q<M && (A[p][q+1]==32) && !tmin[p][q+1])
        {
            C.push(p);
            D.push(q+1);
            tmin[p][q+1]=tmin[p][q]+1;
        }
        if (p<N && q>1 && (A[p+1][q-1]==32) && !tmin[p+1][q-1])
        {
            C.push(p+1);
            D.push(q-1);
            tmin[p+1][q-1]=tmin[p][q]+1;
        }
        if (p<N && (A[p+1][q]==32) && !tmin[p+1][q])
        {
            C.push(p+1);
            D.push(q);
            tmin[p+1][q]=tmin[p][q]+1;
        }
        if (p<N && q<M && (A[p+1][q+1]==32) && !tmin[p+1][q+1])
        {
            C.push(p+1);
            D.push(q+1);
            tmin[p+1][q+1]=tmin[p][q]+1;
        }
    }
}

int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");

    int i, j,Ri,Rj,Ji,Jj ;

    string line ;

    f>>N>>M ;
    getline(f,line);

    for (i=1; i<=N; ++i)
    {
        getline(f,line);
        for (j=1; j<=M; ++j)
        {
            A[i][j] = line[j-1];
            if (A[i][j]=='R')
            {
                Ri=i;
                Rj=j;
            }
            if (A[i][j]=='J')
            {
                Ji=i;
                Jj=j;
            }

        }

    }
    int **tminR = new int*[120] ;
    int **tminJ = new int*[120] ;
    for (i=0; i<=N; ++i)
    {
        tminR[i] = new int[120] ;
        tminJ[i] = new int[120] ;
        for (j=0; j<=M; ++j)
        {
            tminR[i][j]=0;
            tminJ[i][j]=0;
        }
    }

    functie(Ri,Rj,tminR);
    functie(Ji,Jj,tminJ);

    for (i=1;i<=N;++i)
     for  (j=1;j<=M;++j)
     if(tminR[i][j]==tminJ[i][j] && tminR[i][j]>0) {g<<tminR[i][j]+1<<" "<<i<<" "<<j;return 0;}

    return 0 ;
}