Consider a maze of size N by M.
Each cell of the maze may be either free, or occupied by a wall. The maze is
surrounded by a wall, which has two free cells, entry and exit. The entry is
always in the left border of the maze, while the exit is in the right. It is
allowed to move in four directions: up, down, left, right. Diagonal moves are forbidden. There is
always a path between the entry and the exit.
Such a maze may have several possible paths between the
entry and the exit. However, there are cells that will be visited in any case.
Write a program to calculate the number of cells belonging to each path
from the entry to the exit.
Limitations
3 ≤ N, M ≤ 999
Input
The first line contains two integer numbers N
and M, the dimensions of the maze. The following N
lines of M characters describe the maze. Character "#" denotes a wall, and character '.' denotes a free cell.
Output
The output file must contain a single integer – the number of
cells belonging to each path from the entry to the exit.
Sample
|
Standard input
|
Standard output
|
7 7
#######
....#.#
#.#.###
#.....#
###.#.#
#.#....
#######
|
5
|
