375. Shortest Way Through the Maze
A maze is given as a grid of . for open and # for wall. Starting at the
top-left cell, print the fewest moves needed to reach the bottom-right cell,
moving up, down, left or right onto open cells only.
Print -1 if there is no way through.
Every move costs the same, so this is breadth-first search, not something cleverer. Depth-first search will find A route and it will usually be longer than the shortest one, which is the mistake to avoid here.
Watch the two ends. The start may itself be a wall, and so may the target; both answer -1. And when the maze is a single cell the answer is 0, because you are already there.
Constraints - `1 ≤ r ≤ 1000` - `1 ≤ c ≤ 1000` - Every character is `.` or `#`.
Input
The first line contains two integers r and c, the number of rows and
columns. Each of the next r lines contains c characters, each . or #.
Output
Print one integer, the fewest moves, or -1 if the bottom-right cell cannot be
reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.