aig0016   2년 전

문제

옛날에 Bajtocja에서는 도시 A와 B를 연결하는 n개의 차선이 있는 고속도로를 건설했습니다. 그러나 이 도로는 매우 붐벼서 일부 구간은 통행이 불가능하게 되었습니다.

도시 A에 사는 Bajtek은 운전할 때 핸들을 너무 많이 돌리는 것을 좋아하지 않습니다. 그는 차선을 최소한으로 변경하면서 도시 B로 가는 방법을 고민하고 있습니다.

Bajtek은 여행을 어떤 차선에서든지 시작할 수 있고, 마칠 때도 어떤 차선에서든지 종료할 수 있습니다. 고속도로의 교통 규칙에 따라 유턴이나 후진은 허용되지 않습니다.

입력

표준 입력의 첫 번째 줄에는 두 개의 정수 n과 m (1 ≤ n, m ≤ 1 000)이 주어집니다. 다음 n개의 줄에는 각각의 차선에 대한 설명이 포함되어 있습니다. 각 줄에는 m개의 정수가 주어집니다: 0은 고속도로의 통행 가능한 구간을 나타내고, 1은 통행 불가능한 구간을 나타냅니다.

출력

표준 출력의 첫 번째 줄에는 최소한의 차선 변경 횟수를 나타내는 하나의 정수를 출력하거나, 고속도로를 통과할 수 없는 경우 "NIE"라는 단어를 출력해야 합니다.


iktk   1년 전

차선의 변경은 양 옆 차로(배열에서는 위/아래 방향)으로 1칸 이동하는 것을 말합니다.

댓글을 작성하려면 로그인해야 합니다.