Cod sursa(job #2665792)

Utilizator paulaiugaPaula Iuga paulaiuga Data 31 octombrie 2020 12:27:08
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

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


struct celula
{
    int lin, col;
};

int matrixR [106][106], matrixJ [106][106], N, M;
int dx[8] = {0,  0, -1, -1, -1,  1, 1,  1};///vectori de coordonate pt. deplasarile pe celulele vecine
int dy[8] = {1, -1, -1,  1,  0, -1, 0,  1};


void Lee(celula x, int matrix[][106])
{
    queue <celula> celule_speciale;
    celule_speciale.push(x);
    matrix[x.lin][x.col] = 1;

    while (!celule_speciale.empty()) ///cat timp coada de celule speciale nu este goala calculam cu algoritmul lui Lee costul fiecarui
        ///drum de la o celula libera (.) (distanta minima) la una speciala si le adunam
    {
        celula nod = celule_speciale.front();
        celule_speciale.pop();

        //matrix[nod.lin][nod.col] = 1;

        for (int vecin = 0; vecin <= 7; vecin++)
        {
            int lin = nod.lin + dy[vecin];
            int col = nod.col + dx[vecin];

            if (lin < N && col < M && lin >= 0 && col >= 0 && matrix[lin][col] == 0)
            {    celula noua;
                 noua.lin = lin;
                 noua.col = col;
                celule_speciale.push({lin,col});///adugam in coada noua celula pe care am parcurs-o
                matrix[lin][col] = matrix[nod.lin][nod.col] + 1;///nu o mai vizitam o data
            }
        }
    }

}

int main()
{
    celula R,J;///locurile unde se afla ROMEO si JULIETA
    char s[150];

    in>> N >> M;
    in.get();
    for (int i = 0; i < N; i++)
    {
        in.getline(s,150);
        for (int j = 0; j < M; j++)
        {

            if(s[j] == 'R')
            {
                matrixR[i][j] = matrixJ[i][j] =  0;
                R.lin = i;
                R.col = j;

            }
            else if(s[j] == 'J')
            {
                matrixR[i][j] = matrixJ[i][j] =  0;
                J.lin = i;
                J.col = j;
            }
            else if(s[j] == 'X')
            {
                matrixR[i][j] = matrixJ[i][j] =  -1;
            }
            else if(s[j] == ' ')
            {
                matrixR[i][j] = matrixJ[i][j] =  0;
            }
        }
    }

//    for(int i = 0; i < N; i++)
//    {
//        for(int j = 0; j < M ; j++)
//        {
//            cout<<matrixR[i][j]<<" ";
//
//        }
//        cout<<"\n";
//    }
//    cout<<"yes\n";
//
     Lee(R, matrixR);
//
//     for(int i = 0; i < N; i++)
//    {
//        for(int j = 0; j < M ; j++)
//        {
//            cout<<matrixR[i][j]<<" ";
//
//        }
//        cout<<"\n";
//    }
//    cout<<"yes";

   Lee(J, matrixJ);
  //  cout<<"yes";

    int min = INT_MAX;
    celula intalnire;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (matrixR[i][j] > 0 && matrixR[i][j] == matrixJ[i][j] && matrixR[i][j] < min)
            {
                min = matrixR[i][j];
                intalnire.lin = i;
                intalnire.col = j;
            }
        }
    }

    out<<min<<" "<<intalnire.lin + 1 << " "<< intalnire.col + 1<<"\n";




    return 0;
}