2526 寻找路径

时间限制 : 2000/1000 MS(Java/Others) | 内存限制 : 65536/32768 KB(Java/Others)

Submits : 3 | Solved : 2

题目描述

xuenene迷路了!

幸运的是他找到了一张地图,地图上只有一个由 * x 构成的M*N的矩阵,并标注了当前位置位于矩阵左上角,出口在矩阵右下角。

机智的xuenene 猜测 * 表示此地可达, x 表示此地不可达。

为了不再次迷路,他决定只走横路和纵路,而不走歪路,即每次只能向上、向下、向左或向右移动一步。

可是xuenene很懒,他希望经过每个点时所走的路程不超过起点到该点的曼哈顿距离。

曼哈顿距离:两个点在标准坐标系上的绝对轴距总和。

p(x1,y1)  q(x2,y2)          D(p,q) = |x1-x2| + |y1-y2|

现在,他想知道满足上述条件的路共有几条?

虽然xuenene计算能力很强,但他毕竟还是普通人,受不了太大的数字,so 结果对1000000007取模。


输入要求

多组数据,不超过100组,EOF结束,。每组先输入MN。接着输入由 * x 构成的M*N的矩阵, 1 < M,N <=100

保证起点位置为 *


输出要求

 输出路径条数,结果对1000000007取模。


输入样例

2 2
**
**
3 3
***
*x*
***
4 4
****
****
****
***x

输出样例

2
2
0

提示


来源

NBU xuenene


[ 返回顶端 ] | [ 代码提交 ]