A grid has open cells . and walls #. Starting at the top-left cell, move up, down, left or right one cell at a time through open cells. Print the fewest moves needed to reach the bottom-right cell, or -1 if it cannot be reached (including when either corner is a wall).
Constraints
- 1 ≤ R, C ≤ 1000
Input and output
- Input
- Line 1: R C Next R lines: C characters each
- Output
- One integer: the number of moves, or -1.
Examples
Input 1
3 3
..#
#..
#..Output
44 moves.
Input 2
2 2
.#
#.Output
-1Blocked.
Show hints
- Every move costs the same, so the first time BFS reaches a cell is the shortest way there.
Show the explanation
Breadth-first search from the start, storing the distance to each cell the first time it is reached. Because all moves have equal cost, BFS visits cells in increasing distance, so the first time the target is popped we have the answer. O(R·C) time and space. DFS does not give shortest paths here.
Original UniCircle question. Last reviewed 21 Oct 2026.