Walking the Maze

Problem Background

Special for beginners, ^_^

Problem Description

A maze consists of a grid of $R$ rows and $C$ columns. Some cells contain obstacles and cannot be entered; the others are open ground and can be walked on.

Given a maze, find the minimum number of steps from the top-left cell to the bottom-right cell (the data guarantees a path always exists). You may only move horizontally or vertically, never diagonally.

Input Format

The first line contains two integers, $R$ and $C$, the height and width of the maze ($1 \le R, C \le 40$).

Then follow $R$ lines, each with $C$ characters, describing the whole maze.

• . denotes an open cell.
• # denotes a cell with an obstacle.

The top-left and bottom-right cells are both ..

Output Format

Print the minimum number of cells (open cells) that must be passed through from the top-left to the bottom-right, counting both the start and the end cells.

Sample Input

5 5
..###
#....
#.#.#
#.#.#
#.#..

Sample Output

9

Constraints

$1 \le R, C \le 40$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• A plain 2D BFS (or even 0-1 BFS) gives the shortest path; every step costs 1, so the first time you reach the bottom-right is the answer.
• "Counting the start and end" means a BFS that records distance, starting at distance $1$ for the source, will print exactly what is asked.