Little Joseph is in a maze and has to collect all the treasure in the maze. Since Little Joseph likes even numbers, any grid that is marked with an even number is a grid with a treasure.
However, the maze is constructed in such a way that he can only move right on even rows (row 0, 2, 4, etc) and move left on odd rows (row 1, 3, 5 etc). At any grid he can move down to the next row.
Starting at grid[0,0] and ending at any grid cell on the last row, what is the minimum number of moves he has to make (a move is a movement from one grid to another) to get from the start grid to the last grid and collecting all the treasure he can?
You are also given that every row will have at least one treasure in its grid.
The first line consists of the maze width W and height H.
The next H lines consist of W digits (from 0 to 9) and this indicates the number on that grid.
You are to output the minimum number of moves Little Joseph has to make to collect all the treasure he can.
For 30% of the test cases, W < 100, H < 100.
For 60% of the test cases, W < 1000, H < 1000.
For 100% of the test cases, W * H < 10000000.
Sample Input 1
Sample Output 1
He moves right from grid[0,0] to grid[0,4] (4 moves), moves down to grid[1,4] (1 move), moves left from grid[1,4] to grid[1,1] (3 moves), moves down to grid[2,1] (1 move) and lastly moves right from grid[2,1] to grid[2,3] (2 moves), making it a total of 11 moves.