Question

Am o intrebare la algoritmul lui Lee , pentru drum minim in matrice de NxN, (folosing biblioteca ); daca am urmatorul enunt : Se da o matrice in care daca elementul este X nu poti traversa prin acea casuta,daca este caracterul punct (.) atunci trebuie sa aflii pentru acea casuta drumul minim pana la o casuta unde se afla mancare,si daca este caracterul P atunci inseamna ca in acea casuta se afla mancare : de ex urmatoarea matrice :
8
...#....
#..#..#.
.##.P..#
..#.#.#.
........
........
###...##
..P.....
Ce nu inteleg eu la aceasta aplicatie a algoritmului este de ce daca eu bag in coada pozitiile unde e 'P' , si cand fac algortimul intreb : daca lee[i][j] != 0 nu e valid. adica daca pentru un P gasesc un drum de 8 pana la un '.' si pe pozitia in matrice a punctului va fi 8 , dar acela nu e drumul minim pentru ca de ex mai era o alta mancare mai aproape,dar in algoritm dupa ce un element ia o valoare(adica lungimea drumului) nu mai poate sa isi schimbe valoarea pentru ca atunci cand faci vecinii conditia e : mat[i][j] == 1 && lee[i][j] != 0. nu stiu daca am fost destul de clar dar ca idee nu inteleg de ce daca o pozitie din matrice poate lua o singura data o valoare cum stim ca e minima si nu mai exista alt drum pentru care era mai scurt , si daca tot n ati inteles ce nu inteleg pur si simplu rezolvati problema pas cu pas si explicati cum functioneaza : asta e codul meu puteti explica direct pe al meu ce face fiecare instructiune :
#include
#include
 
using namespace std;
 
ifstream fin("brainly.in");
ofstream fout("brainly.out");
 
int di[] = {0,0,-1,1}, dj[] = {-1,1,0,0};
int n;
 
int v[255][255];
 
queue < pair < int, int > > Q;
 
bool ok(int i,int j)
{
    if (v[i][j] == -1) return 1;
    return 0;
}
 
int main()
{
    int i,j,n,i_nou,j_nou;
    char c;
    fin >> n;
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            fin >> c;
            if (c == 'P')
            {
                Q.push(make_pair(i,j));
            }
            else if (c == '#') v[i][j] = -2;
            else v[i][j] = -1;
        }
    }
    while (!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        for (int k = 0; k < 4; ++k)
        {
            i_nou = i + di[k];
            j_nou = j + dj[k];
            if (ok(i_nou,j_nou))
            {
                Q.push(make_pair(i_nou,j_nou));
                v[i_nou][j_nou] = v[i][j] + 1;
            }
        }
        Q.pop();
    }
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            fout << v[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;
}

Answer 1

Algoritmul se bazeaza pe faptul ca tu vizitezi prima data toate celulele matricei care sunt la distanta 1, ele nu au cum sa fie la o distanta mai mica de 1. Avand acest lucru completat, le vizitezi pe cele la distanta 2, ele nu pot fi mai aproape pentru ca altfel le-ai fi gasit la pasul anterior.