有一个 $H$ 行 $W$ 列的迷宫(行号从上到下是 $1 - H$,列号从左到右是 $1 - W$),现在有一个由 .
和 #
组成的 H
行 W
列的矩阵表示这个迷宫的构造,.
代表可以通过的空地,#
代表不能通过的墙。
现在有个人从 起点 $(1, 1)$ 开始走,他每一步只能往右走一格或者往下走一格,并且他不能跨越迷宫的边界。他会一直走,直到没有可以走的路时停下来。
请问这个人最多可以经过多少个格子?
输入格式
第一行两个整数 $H$,$W$,表示迷宫有 $H$ 行 $W$ 列。
接下来一个 $H$ 行 $W$ 列的由 .
和 #
组成的矩阵,表示迷宫的构造。
注意:保证 $(1, 1)$ 的位置一定是 .
。
输出格式
一个整数,表示最多步数。
样例输入1
3 4
.#..
..#.
..##
样例输出1
4
样例输入2
1 1
.
样例输出2
1
样例输入3
5 5
.....
.....
.....
.....
.....
样例输出3
9
数据规模
对于全部数据保证 $1 \leq H,W \leq100$