Cod sursa(job #2133340)

Utilizator TheDarkLordDascalescu Mihai TheDarkLord Data 16 februarie 2018 20:12:32
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <fstream>
#include <queue>
#include <cstring>

#define LMax 100

using namespace std;

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

const int dx[]={1, -1, 1, -1, 0, 1, 0, -1};
const int dy[]={1, -1, -1, 1, 1, 0, -1, 0};

int n, m, Oras[LMax+5][LMax+5];

int rx, ry, jx, jy;

int l=101, c=101, d=10100;

bool Vizitat[LMax+5][LMax+5];

queue < pair < int, int > > coada;

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

void LeeR (int x, int y)
{
    coada.push(make_pair(x,y));
    Vizitat[x][y]=1;
    while(!coada.empty())
    {
        int i=coada.front().first;
        int j=coada.front().second;
        coada.pop();
        for(int dir=0;dir<8;dir++)
        {
            int i_new=i+dx[dir];
            int j_new=j+dy[dir];
            if(!Vizitat[i_new][j_new])
            {
                Oras[i_new][j_new]=Oras[i][j]+1;
                Vizitat[i_new][j_new]=1;
                coada.push(make_pair(i_new,j_new));
            }
        }
    }
    Oras[jx][jy]=0;
}

void LeeJ (int x, int y)
{
    memset(Vizitat, 0, sizeof Vizitat);
    coada.push(make_pair(x,y));
    Vizitat[x][y]=1;
    while(!coada.empty())
    {
        int i=coada.front().first;
        int j=coada.front().second;
        coada.pop();
        for(int dir=0;dir<8;dir++)
        {
            int i_new=i+dx[dir];
            int j_new=j+dy[dir];
            if(!Vizitat[i_new][j_new])
            {
                Vizitat[i_new][j_new]=1;
                int aux=Oras[i][j]+1;
                if(aux<=Oras[i_new][j_new])
                {
                    if(aux<Oras[i_new][j_new])
                    {
                        Oras[i_new][j_new]=aux;
                        coada.push(make_pair(i_new,j_new));
                    }
                    else
                    {
                        if(aux<=d)
                        {
                            if(aux<d)
                            {
                                d=aux;
                                l=i_new;
                                c=j_new;
                            }
                            else
                            {
                                if(i_new<=l)
                                {
                                    if(i_new<l)
                                    {
                                        l=i_new;
                                        c=j_new;
                                    }
                                    else
                                    {
                                        if(j_new<c)
                                        {
                                            int l=i_new;
                                            int c=j_new;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main ()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char x[102];
        fin.get();
        fin.get(x,102);
        for(int j=0;j<m;j++)
        {
            if(x[j]=='X')
                Vizitat[i][j+1]=1;
            else if(x[j]=='R')
            {
                    rx=i;
                    ry=j+1;
            }
            else if(x[j]=='J')
            {
                jx=i;
                jy=j+1;
            }
        }
    }
    Bordare ();
    LeeR (rx,ry);
    LeeJ (jx, jy);
    fout<<d+1<<' '<<l<<' '<<c;
}