Cod sursa(job #2148972)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 2 martie 2018 11:00:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

struct coada
{
    int linie1,coloana1;
};

int N,M,A[105][105],Q[105][105],linie,coloana,linieR,coloanaR,linieJ,coloanaJ,i;
char V[105][105],aux;
int Rl[9]= {0,-1,-1,0,1,1,1,0,-1};
int Rc[9]= {0,0,1,1,1,0,-1,-1,-1};
int liniemin,coloanamin,tmin=9999999;
int prim,ultim;
coada C[10000];

int main()
{
    fin>>N>>M;
    fin.get(aux);
    for (linie=1; linie<=N; linie++)
    {
        for (coloana=1; coloana<=M+1; coloana++)
            fin.get(V[linie][coloana]);
    }
    for (linie=1; linie<=N; linie++)
    {
        for (coloana=1; coloana<=M; coloana++)
        {
            if (V[linie][coloana]=='X')
            {
                A[linie][coloana]=-1;
                Q[linie][coloana]=-1;
            }
            else if (V[linie][coloana]=='R')
            {
                linieR=linie;
                coloanaR=coloana;
            }
            else if (V[linie][coloana]=='J')
            {
                linieJ=linie;
                coloanaJ=coloana;
            }
            else
            {
                Q[linie][coloana]=0;
                A[linie][coloana]=0;
            }
        }
    }
    for (i=0; i<=N+1; i++)
    {
        A[i][0]=1;
        Q[i][0]=1;
        A[i][M+1]=1;
        Q[i][M+1]=1;
    }
    for (i=0; i<=M+1; i++)
    {
        A[0][i]=1;
        Q[0][i]=1;
        A[N+1][i]=1;
        Q[N+1][i]=1;
    }
    prim=1;
    ultim=1;
    C[prim].linie1=linieR;
    C[prim].coloana1=coloanaR;
    A[linieR][coloanaR]=1;
    while (prim<=ultim&&A[linieJ][coloanaJ]==0)
    {
        linie=C[prim].linie1;
        coloana=C[prim].coloana1;
        C[prim].linie1=0;
        C[prim].coloana1=0;
        prim++;
        for (i=1; i<=8; i++)
        {
            if (A[linie+Rl[i]][coloana+Rc[i]]==0)
            {
                ultim++;
                C[ultim].linie1=linie+Rl[i];
                C[ultim].coloana1=coloana+Rc[i];
                A[linie+Rl[i]][coloana+Rc[i]]=A[linie][coloana]+1;
            }
        }
    }
    prim=1;
    ultim=1;
    C[prim].linie1=linieJ;
    C[prim].coloana1=coloanaJ;
    Q[linieJ][coloanaJ]=1;
    while (prim<=ultim)
    {
        linie=C[prim].linie1;
        coloana=C[prim].coloana1;
        C[prim].linie1=0;
        C[prim].coloana1=0;
        prim++;
        for (i=1; i<=8; i++)
        {
            if (Q[linie+Rl[i]][coloana+Rc[i]]==0)
            {
                ultim++;
                C[ultim].linie1=linie+Rl[i];
                C[ultim].coloana1=coloana+Rc[i];
                Q[linie+Rl[i]][coloana+Rc[i]]=Q[linie][coloana]+1;
            }
        }
    }
    for (linie=1;linie<=N;linie++)
     for (coloana=1;coloana<=M;coloana++)
    {
     if ((Q[linie][coloana]==A[linie][coloana])&&Q[linie][coloana]>1)
                {
                    if (A[linie][coloana]<tmin)
                    {
                     liniemin=linie;
                     coloanamin=coloana;
                     tmin=Q[linie][coloana];
                    }
                }
    }
    fout<<tmin<<" "<<liniemin<<" "<<coloanamin;
    return 0;
}