47 - DFS图的遍历

JM在一个n*m的网格迷宫中,"#"表示墙,不可以走,"."表示空地,可以走。

从左上角(1,1)出发,想走到(n,m)位置,每次可以往上下左右四个方向移动一步,不会走已经走过的位置,也不会走到网格迷宫外面去。

现在JM想知道,从(1,1)出发到(n,m)他有多少种移动步数最少的方案。

输入

第一行输入两个整数n,m,表示网格迷宫的大小

接下来输入n行m列个字符,只包含"#"和"."

输出

输出移动步数最少的不同方案数

样例

输入

3 5
..#..
#....
...#.

输出

1

输入

3 4
....
....
....

输出

10

提示

数据规模

对于100%的数据,n,m<=10

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题