Algoritmi → Grafovi i stabla → Zadatak: Najkraći put u lavirintu

Najkraći put u lavirintu (BFS)

Zadatak

Lavirint je matrica n × m (n, m ≤ 1000) sa znakovima: S – start, C – cilj, . – prolaz, # – zid. U jednom koraku prelazi se na susedno polje (gore, dole, levo, desno). Ispiši najmanji broj koraka od S do C i lavirint u kome je jedan najkraći put označen zvezdicama. Ako put ne postoji, ispiši -1.

4 6
S..#..
.#.#.#
.#...C
...##.

7
S**#..
.#*#.#
.#***C
...##.

Ideja rešenja

1. Iz starta pokreni BFS. Niz dist čuva udaljenost svakog polja od starta (−1 = još neposećeno).
2. Kada se polje ubacuje u red, njegova udaljenost je udaljenost tekućeg polja plus 1, a u niz odakle se zapisuje iz kog polja smo došli.
3. Kad BFS završi, dist cilja je dužina najkraćeg puta. Put se rekonstruiše unazad: od cilja, preko odakle, do starta.

Svako polje ulazi u red najviše jednom, pa je složenost O(n · m). BFS daje najkraći put samo kada svi koraci imaju istu cenu; za različite cene koristi se Dijkstrin algoritam.

Rešenje (C++)

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> lav(n);
    for (auto &red : lav) cin >> red;

    int sr = 0, sk = 0, cr = 0, ck = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (lav[i][j] == 'S') { sr = i; sk = j; }
            if (lav[i][j] == 'C') { cr = i; ck = j; }
        }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<pair<int, int>>> odakle(n, vector<pair<int, int>>(m, {-1, -1}));
    int dr[] = {-1, 1, 0, 0}, dk[] = {0, 0, -1, 1};

    queue<pair<int, int>> red;
    red.push({sr, sk});
    dist[sr][sk] = 0;
    while (!red.empty()) {
        auto [r, k] = red.front();
        red.pop();
        if (r == cr && k == ck) break;                 // cilj je dostignut najkraćim putem
        for (int s = 0; s < 4; s++) {
            int nr = r + dr[s], nk = k + dk[s];
            if (nr < 0 || nr >= n || nk < 0 || nk >= m) continue;
            if (lav[nr][nk] == '#' || dist[nr][nk] != -1) continue;
            dist[nr][nk] = dist[r][k] + 1;
            odakle[nr][nk] = {r, k};
            red.push({nr, nk});
        }
    }

    if (dist[cr][ck] == -1) {
        cout << -1 << endl;
        return 0;
    }
    cout << dist[cr][ck] << "\n";
    // rekonstrukcija puta unazad, bez starta i cilja
    auto [r, k] = odakle[cr][ck];
    while (!(r == sr && k == sk)) {
        lav[r][k] = '*';
        auto p = odakle[r][k];
        r = p.first;
        k = p.second;
    }
    for (auto &red2 : lav) cout << red2 << "\n";
    return 0;
}

Redosled pomeraja (gore, dole, levo, desno) određuje koji od više najkraćih puteva će biti ispisan; dužina je uvek ista.

Varijante zadatka

• Više startova (npr. požar se širi iz više polja): u red se na početku ubace svi startovi sa udaljenošću 0.
• Ključevi i vrata: stanje nije samo polje, nego polje + skup ključeva – BFS po stanjima.
• Kretanje kao skakač (šahovski konj): menjaju se samo nizovi pomeraja.

Proveri znanje