Pepe the frog needs to jump across a river while only stepping on some stones! He needs to jump from column to column (left to right in the input). Rock means the rock on row . However, jumping from row to takes time.
The first line of the input contains two integers, and , the number of columns and the number of positions of rocks.
Each subsequent lines of the input contains of a string of
1 on line (starting from 2nd line) on column (both 0-indexed) indicates the rock is present in column , a
0 indicates that rock is not present.
Output the minimum amount of time taken to jump to the end.
You are guaranteed there is at least one possible way to jump to the end.
Subtask 1 (10%)
Subtask 2 (5%)
Subtask 3 (20%)
Subtask 4 (20%)
Subtask 5 (45%)
Sample Input 1
5 3 11100 00011 11111
Sample Output 1
Sample Input 1 Explanation
You don't need to jump, just use rock 3 throughout.
Sample Input 2
5 5 10000 01000 00100 00010 00001
Sample Output 2
Sample Input 2 Explanation
Start from rock 0, change to rock 1, change to rock 2, etc. Each of them takes 1 time because they are adjacent.