Drumuri cu obstacole: programare dinamică în C++

O matrice descrie o hartă în care unele celule sunt blocate. Pornim din colțul stânga sus și vrem să ajungem în colțul dreapta jos, deplasându-ne numai la dreapta sau în jos. Numărăm drumurile care nu intră în nicio celulă blocată.

Aceasta este o extensie a problemei fără obstacole. Modificarea nu constă doar într-o condiție pusă la întâmplare în buclă: trebuie redefinit ce înseamnă un drum valid, verificată celula de start și păstrată corect baza recurenței.

Cum funcționează

Definim d[i][j] ca numărul drumurilor valide de la (1,1) până la (i,j), calculat modulo 1000000007. Pentru o celulă blocată, valoarea este zero. Pentru start, valoarea este unu numai dacă acesta este liber. Pentru orice altă celulă liberă, ultimul pas vine de sus sau din stânga, deci adunăm d[i-1][j] și d[i][j-1].

Folosim linia zero și coloana zero ca margini artificiale cu valoarea zero. Ele nu sunt celule ale hărții. Astfel, pentru prima linie contribuția de sus dispare, iar pentru prima coloană dispare contribuția din stânga. Nu trebuie să scriem patru formule diferite pentru margini și interior.

Verificarea obstacolului precedă verificarea startului. Dacă am atribui necondiționat d[1][1]=1 după calculul celulelor blocate, am inventa un drum care pornește printr-un obstacol. Aceeași regulă dă automat zero atunci când destinația este blocată.

Parcurgem liniile de sus în jos și coloanele de la stânga la dreapta. Cele două dependențe sunt deja rezolvate. Dacă am permite și pași în sus, graful dependențelor ar putea conține cicluri și formula nu ar mai număra același tip de drumuri.

Intrarea conține n și m, cu 1<=n,m<=50, apoi n*m valori: 0 înseamnă liber, 1 înseamnă blocat. Ieșirea este numărul drumurilor modulo 1000000007. Chiar fără obstacole, numărul exact pentru dimensiuni mari poate depăși long long; reducerea modulo face parte din cerință, nu este o aproximare accidentală.

Tablourile clasice au capacitate 51 pe fiecare dimensiune. Harta logică are n*m celule indexate de la unu; marginea zero este rezervată pentru baze. În std::vector alocăm n+1 linii, fiecare cu m+1 elemente, folosind aceeași indexare. Dimensiunea logică a problemei nu devine 51x51 doar fiindcă aceasta este capacitatea disponibilă.

Exemplu urmărit pas cu pas

Pentru o hartă 3x3 cu centrul blocat, X marchează obstacolul:

hartă                 număr de drumuri
0  0  0               1  1  1
0  X  0               1  0  1
0  0  0               1  1  2

La (2,3) avem 1+0=1: sosirea din stânga este imposibilă. La (3,3) avem 1+1=2. Cele două trasee ocolesc centrul pe marginea de sus și din dreapta, respectiv pe marginea din stânga și de jos. Harta și tabelul nu sunt același lucru: un zero în d poate indica și o celulă liberă, dar inaccesibilă.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    int blocked[51][51] = {};
    long long d[51][51] = {};
    const long long MOD = 1000000007;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            std::cin >> blocked[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (blocked[i][j]) {
                d[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1)
                d[i][j] = 1;
            else
                d[i][j] = (d[i - 1][j] + d[i][j - 1]) % MOD;
        }
    std::cout << d[n][m] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> blocked(n + 1, std::vector<int>(m + 1, 0));
    std::vector<std::vector<long long>> d(n + 1, std::vector<long long>(m + 1, 0));
    const long long MOD = 1000000007;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            std::cin >> blocked[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (blocked[i][j]) {
                d[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1)
                d[i][j] = 1;
            else
                d[i][j] = (d[i - 1][j] + d[i][j - 1]) % MOD;
        }
    std::cout << d[n][m] << '\n';
}

De ce funcționează și cât costă

Un drum valid către o celulă liberă, diferită de start, are exact unul dintre cele două ultime segmente. Eliminarea lui produce un drum valid către vecin. Nicio tranziție nu intră într-un obstacol, deoarece starea acelui obstacol este zero. Inducția în ordinea de parcurgere justifică toate stările.

Timpul este O(nm), iar memoria este O(nm). Dacă vrem doar numărul final, putem păstra o singură linie de stări, dar fiecare obstacol trebuie să suprascrie explicit valoarea curentă cu zero.

Greșeli frecvente

Nu pune automat unu pe toată prima linie sau coloană: după primul obstacol, celulele următoare pot fi inaccesibile. Nu considera zero în tabel echivalent cu obstacol. Nu permite pași diagonali dacă formula și cerința includ numai dreapta și jos.

Exersează

Într-o matrice 2x3, blochează celula (1,2). Calculează tabelul și descrie drumul rămas. Apoi blochează și (2,2).

Rezolvare explicată: Prima linie a stărilor este 1,0,0, iar a doua este 1,1,1. Singurul drum începe în jos și continuă de două ori la dreapta. Cu ambele celule din coloana doi blocate, răspunsul devine zero.

Probleme de practică

Rezolvă cele trei probleme în ordinea de mai jos. Deschide fiecare problemă, scrie soluția și verific-o folosind testele locale din pagină. Respectă formatul de intrare, limitele și ieșirea cerută; acestea pot diferi de programul din lecție. Trimiterea pentru punctaj necesită autentificare și un evaluator activ.

1. Drumuri printre obstacole. Aplică direct lecția, cu atenție la celulele blocate și la capetele traseului. Ca în lecție, 0 înseamnă liber și 1 înseamnă obstacol; dimensiunile maxime ale matricei sunt cele din enunț.

2. Drumuri cu trei direcții. Variație fără obstacole: adaugă deplasarea diagonală și identifică toate celulele precedente. Rezultatul se cere exact, fără modulo.

3. Drum ieftin cu diagonală. Extensie: păstrează cele trei direcții, dar calculează costul minim în loc să numeri traseele. Respectă includerea primei și ultimei celule în cost.

Continuă să înveți

Înapoi la programarea dinamică. Recapitulează tablourile și recursivitatea.

Întrebări frecvente

Ce afișăm dacă startul este blocat?

Zero. Nu există nici măcar drumul vid valid într-o celulă în care nu avem voie să intrăm.

Ce se întâmplă pe o hartă 1x1 liberă?

Există exact un drum fără deplasări. Startul coincide cu destinația, deci răspunsul este unu.

De ce nu adunăm și vecinul diagonal?

Mișcările permise sunt numai dreapta și jos. O altă tranziție ar număra drumuri pe care cerința nu le permite.

Un rezultat zero înseamnă mereu că nu există drum?

Înainte de modulo, da. După modulo, un număr pozitiv multiplu de modul poate avea rest zero. Nu folosi restul pentru a decide existența în general.

Pot reconstrui un drum doar din aceste resturi?

Nu în general: restul zero poate ascunde existența unor drumuri. Pentru reconstruire, păstrează separat accesibilitatea sau un predecessor valid.