Mai intai trebuie sa te autentifici.

Cod sursa(job #1921988)

Utilizator vladrares10Raducu Vlad-Rares vladrares10 Data 10 martie 2017 15:35:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

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

int N,M;
int Map[105][105];
int Map2[105][105];
char s[105];
int startrx,startry,startjx,startjy;
int ii,jj,timp=-1;
int di[8] = {0,0,1,-1,-1,1,-1,1};
int dj[8] = {1,-1,0,0,1,1,-1,-1};

queue < pair <int,int> > coada;

void Read()
{
    fin >> N >> M;
    fin.get();
    for(int i = 1; i <= N; i++)
    {

        fin.getline(s,102);
        for(int j = 0; j < M; j++)
        {
            if(s[j] == 'R')
            {
                startrx = i;
                startry = j+1;

            }
            if(s[j] == 'J')
            {
                startjx = i;
                startjy = j+1;

            }
            if(s[j] == 'X')
            {
                Map[i][j+1] = -1;
                Map2[i][j+1] = -1;
            }

        }

    }

}

bool OK(int i, int j)
{
    if(i < 1 or j < 1 or i > N or j > M)
        return false;
    if(Map[i][j] != 0)
        return false;
    return true;
}
bool OK2(int i, int j)
{
    if(i < 1 or j < 1 or i > N or j > M)
        return false;
    if(Map2[i][j] != 0)
        return false;
    return true;
}

void Lee1()
{
    int i,j;
    int i_urm,j_urm;
    Map[startrx][startry] = 1;
    coada.push(make_pair(startrx,startry));
    while(!coada.empty())
    {
        i = coada.front().first;
        j = coada.front().second;
        coada.pop();
        for(int directie = 0; directie < 8; directie++)
        {
            i_urm = i + di[directie];
            j_urm = j + dj[directie];
            if(OK(i_urm,j_urm) and Map[i_urm][j_urm] == 0)
            {
                Map[i_urm][j_urm] = Map[i][j] + 1;
                coada.push(make_pair(i_urm,j_urm));
            }

        }
    }

}
void Lee2()
{
    int i,j;
    int i_urm,j_urm;
    Map2[startjx][startjy] = 1;
    coada.push(make_pair(startjx,startjy));
    while(!coada.empty())
    {
        i = coada.front().first;
        j = coada.front().second;
        coada.pop();
        for(int directie = 0; directie < 8; directie++)
        {
            i_urm = i + di[directie];
            j_urm = j + dj[directie];
            if(OK2(i_urm,j_urm) and Map2[i_urm][j_urm] == 0)
            {
                Map2[i_urm][j_urm] = Map2[i][j] + 1;
                coada.push(make_pair(i_urm,j_urm));
            }

        }
    }

}

int main()
{
    Read();
    Lee1();
    Lee2();

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(Map[i][j] == Map2[i][j] and Map[i][j] > 0)
            {
            if(timp == -1)
            {
                timp = Map[i][j];
                ii = i;
                jj = j;
            }
            else
               if(Map[i][j] == timp)
            {
                if(j < jj)
                {
                    jj = j;
                    ii = i;
                }
                else if(j == jj)
                   ii = i;

            }
            else
                if(Map[i][j] < timp)
            {
                timp = Map[i][j];
                ii = i;
                jj = j;
            }
            }
    fout << timp << " " << ii << " " << jj << "\n";


    return 0;
}