Există un drum?

Verifică dacă există un drum între colțul stânga-sus și colțul dreapta-jos, trecând numai prin celule libere. Date de intrare: Două numere întregi n și m (1 ≤ n,m ≤ 20), apoi n rânduri de exact m caractere 0 sau 1, fără spații. 0 este liber, 1 este perete. Date de ieșire: Textul exact DA dacă poți ajunge din (0,0) în (n-1,m-1) folosind numai pași sus, jos, stânga sau dreapta; altfel NU. Dacă startul sau destinația este perete, răspunsul este NU. Exemplu de intrare: 3 3 000 110 000 Exemplu de ieșire: DA Explicația exemplului: Există drumul (0,0) → (0,1) → (0,2) → (1,2) → (2,2). Poți folosi BFS și o matrice de celule vizitate.

3 3
000
110
000

DA