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