Cerință
Într-o grilă, 1 reprezintă uscat și 0 apă. O insulă este un grup maximal de celule de uscat unite pe laturi. Există exact două insule. Poți transforma celule de apă în uscat. Află numărul minim de celule transformate pentru a uni insulele.
Tip de problemă: Shortest Bridge.
Date de intrare
Se citesc n și m, apoi n linii cu câte m valori 0 sau 1.
Date de ieșire
Afișează numărul minim de celule de apă schimbate.
Restricții
1 ≤ n,m ≤ 100; n·m ≥ 3. Grila conține exact două insule.
Observații
Raportată de un candidat: Shortest Bridge la Uber (L4, screening și rundă de programare; data interviului nu este precizată).
Adaptare Algo25: Grilă dreptunghiulară, vecinătate pe patru direcții și exact două insule.
Sursa relatării: https://leetcode.com/discuss/post/1428371/uber-l4-reject/
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. 1 = uscat; 0 = apă. Două celule de uscat sunt vecine numai dacă au o latură comună.Mărește schema ↗Date de intrare
1 3
1 0 1
Date de ieșire
1
Exemplul 2
Date de intrare
2 2
1 0
0 1
Date de ieșire
1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →