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