BFS cu surse multiple: distanțe într-o matrice C++

Într-o matrice cu mai multe surse, vrem pentru fiecare celulă numărul minim de pași până la oricare dintre ele. Un pas trece într-o celulă vecină pe latură. Dacă lansăm o căutare completă pentru fiecare sursă, repetăm multă muncă. Putem porni din toate sursele simultan.

Ce înseamnă BFS

BFS vine de la Breadth-First Search, în română parcurgere în lățime. Procesăm mai întâi celulele aflate la distanța zero, apoi cele la distanța unu, apoi la distanța doi. O coadă păstrează această ordine: prima celulă introdusă este prima extrasă.

Citim 1≤n,m≤100 și o matrice de zerouri și unu, cu cel puțin un 1. Fiecare 1 reprezintă o sursă; toate celulele sunt traversabile, inclusiv cele cu zero. Nu există obstacole. Afișăm matricea distanțelor minime. Indicii interni sunt de la zero.

Inițializarea face diferența

Punem toate sursele în coadă, fiecare cu distanța zero. Celelalte celule primesc -1, care înseamnă „încă nedescoperită”. Când extragem o celulă cu distanța d, vecinii nedescoperiți primesc d+1 și intră în coadă.

Marcăm distanța la introducere, nu la extragere. Astfel două fronturi care ajung la aceeași celulă nu o introduc de două ori. Nu contează care sursă câștigă o egalitate, deoarece cerința cere doar distanța minimă.

Într-o matrice 3×3 fără obstacole, cu surse în (0,0) și (2,2), distanțele minime sunt 0,1,2 / 1,2,1 / 2,1,0.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[100][100],dist[100][100]; queue<pair<int,int>> q;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
        cin >> a[i][j]; dist[i][j]=-1;
        if(a[i][j]==1) { dist[i][j]=0; q.push({i,j}); }
    }
    int di[4]={-1,0,1,0},dj[4]={0,1,0,-1};
    while(!q.empty()) {
        auto [i,j]=q.front(); q.pop();
        for(int d=0;d<4;++d) {
            int x=i+di[d],y=j+dj[d];
            if(x>=0 && x<n && y>=0 && y<m && dist[x][y]==-1) {
                dist[x][y]=dist[i][j]+1; q.push({x,y});
            }
        }
    }
    for(int i=0;i<n;++i) {
        for(int j=0;j<m;++j) cout << (j?" ":"") << dist[i][j];
        cout << '\n';
    }
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n,vector<int>(m)),dist(n,vector<int>(m)); queue<pair<int,int>> q;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
        cin >> a[i][j]; dist[i][j]=-1;
        if(a[i][j]==1) { dist[i][j]=0; q.push({i,j}); }
    }
    vector<int> di={-1,0,1,0},dj={0,1,0,-1};
    while(!q.empty()) {
        auto [i,j]=q.front(); q.pop();
        for(int d=0;d<4;++d) {
            int x=i+di[d],y=j+dj[d];
            if(x>=0 && x<n && y>=0 && y<m && dist[x][y]==-1) {
                dist[x][y]=dist[i][j]+1; q.push({x,y});
            }
        }
    }
    for(int i=0;i<n;++i) {
        for(int j=0;j<m;++j) cout << (j?" ":"") << dist[i][j];
        cout << '\n';
    }
}

De ce prima distanță găsită este minimă

Coada procesează celulele în ordinea nedescrescătoare a distanței. Înainte să prelucrăm distanța d+1, toate celulele de distanță d au avut șansa de a-și descoperi vecinii. Dacă ar exista un drum mai scurt spre o celulă, acesta ar fi descoperit-o mai devreme.

push adaugă la sfârșit, front citește prima pereche de coordonate, iar pop o elimină. pair<int,int> ține împreună linia și coloana. Verificăm limitele coordonatelor înainte de accesul în matrice.

Fiecare celulă intră o dată în coadă și verifică patru vecini. Timpul este O(n·m), memoria O(n·m) pentru distanțe și coadă. Nu înmulțim timpul cu numărul surselor.

Exersează

Pentru liniile 1 0 0 și 0 0 1, distanțele sunt 0 1 1 și 1 1 0. Cu o singură sursă în colțul unei matrice 2×2, rezultatul este 0 1 / 1 2. Dacă fiecare celulă este sursă, toate distanțele sunt zero.

Revezi parcurgerea în lățime, drumul minim fără costuri și matricele.

Întrebări frecvente

Ce este BFS cu surse multiple?

Este o parcurgere în lățime care pune toate sursele în aceeași coadă de la început, cu distanța zero. Extinderea pe niveluri găsește distanța minimă până la cea mai apropiată sursă.

De ce nu rulez un BFS separat din fiecare sursă?

Ai repeta explorarea acelorași celule. Pornirea simultană procesează fiecare celulă cel mult o dată, într-o matrice cu vecini pe laturi și pași de același cost.

Ce măsoară distanța calculată în matrice?

Numărul minim de pași permiși până la o sursă, nu distanța geometrică în linie dreaptă. Dacă sunt permise doar laturile, o deplasare diagonală nu reprezintă un singur pas.