Labirint: drumul spre ieșire

Găsește numărul minim de mutări din colțul stânga-sus până în colțul dreapta-jos al unui labirint. O mutare trece într-o celulă vecină sus, jos, stânga sau dreapta; nu sunt permise diagonale și nu poți trece prin pereți. Date de intrare: Două numere întregi n și m, urmate de n rânduri de exact m caractere 0 sau 1, fără spații. 0 înseamnă liber, 1 înseamnă perete. Pornirea este în (0,0), iar destinația în (n-1,m-1). Date de ieșire: Un singur număr întreg: numărul minim de mutări prin celule libere sau -1 dacă nu există drum. Dacă pornirea și destinația coincid într-o celulă liberă, rezultatul este 0. Exemplu de intrare: 3 3 000 110 000 Exemplu de ieșire: 4 Explicația exemplului: Traseul minim merge de la (0,0) spre dreapta de două ori, apoi în jos de două ori: patru mutări. BFS explorează celulele în ordinea distanței.

3 3
000
110
000

4