Pasy Ruchu
Limit pamięci: 64 MB
Dawno temu w Bajtocji wybudowano autostradę o pasach ruchu, łączącą
dwa miasta i . Droga była jednak tak uczęszczana, że niektóre jej
fragmenty stały się nieprzejezdne.
Bajtek, mieszkaniec miasta , nie lubi zbyt wiele razy kręcić kierownicą.
Zastanawia się, jak dojechać do miasta , zmieniając pasy ruchu minimalną
liczbę razy.
Bajtek może rozpocząć swoją podróż z dowolnego pasa ruchu i zakończyć
również na dowolnym. Zgodnie z obowiązującymi zasadami ruchu drogowego
na autostradzie nie wolno zawracać ani cofać.
Wejście
Pierwszym wiersz standardowego wejścia zawiera dwie liczby całkowite i
(). W następnych wierszach znajdują się opisy
kolejnych pasów ruchu. Każdy z takich wierszy zawiera liczb całkowitych:
to przejezdny fragment autostrady, natomiast to nieprzejezdny.
Możesz założyć, że w testach wartych punktów zachodzi .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę
całkowitą, równą minimalnej liczbie zmian pasów ruchu,
lub jedno słowo NIE, jeśli przejazd przez autostradę jest niemożliwy.
Przykład
Dla danych wejściowych:
4 5
0 0 0 1 0
0 1 0 1 0
1 1 0 0 0
0 0 1 0 1
poprawną odpowiedzią jest:
2
Autor zadania: Jacek Tomasiewicz.