Description

A maze consists of R rows and C columns of cells. Some cells contain obstacles and cannot be passed, while others are empty and can be traversed. Given a maze, determine the minimum number of steps required to move from the top-left corner to the bottom-right corner (it is guaranteed that a path exists). Movement is only allowed horizontally or vertically, not diagonally.

Input Format

The first line contains two integers, R and C, representing the number of rows and columns of the maze. (1 ≤ R, C ≤ 40)
The following R lines each contain C characters, representing the entire maze.
Empty cells are denoted by '.', and cells with obstacles are denoted by '#'.
The top-left and bottom-right corners of the maze are guaranteed to be '.'.

Output Format

Output the minimum number of steps required to move from the top-left corner to the bottom-right corner (i.e., the minimum number of empty cells that must be traversed). The step count includes both the starting and ending cells.

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

9