Marcus is stuck in a -dimensional grid of size , consisting of
. for walkable spaces and
# for unwalkable spaces! He is at the top left corner (position and must travel to the bottom right corner (position ) through only walkable spaces. He can only move left, right, and down. In a path, let be the number of times he moves down, left, and right, respectively. Let the cost of the path be . Marcus wants to find a path from to that has the minimum cost.
Marcus wants to know the minimum possible cost. Please help him!
The first line will contain the integer , the size of the grid.
The next lines will each contain characters, either
. for a walkable space or
# for an unwalkable space. The first character of the first line will be position and the character of the line will be position .
It is guaranteed positions and will be walkable (
Output the minimum cost path for Marcus. If there is no path, output
Subtask 1 [25%]
Subtask 2 [75%]
No further constraints.
6 ...... .#.... ##.##. ...... .##### ......
Explanation For Sample
The minimum cost path consists of moving down units, left units, and right units, for a total of .