这里有一个 H 行 W 列的矩阵,(i,j) 指从上往下第 i 行,从左往右第 j 列的单元 对于每一个 i,j(1≤i≤H,1≤j≤W) ,单元(i,j) 的内容为一个字符 a i,j 如果 a i,j 的内容是. ,那么代表啥都没有,但如果是 # ,那么说明这是一堵正方形的大墙!并且阿福无法通过大墙!保证 (1,1) 和 (H,W) 是空的 阿福只能从 (1,1) 开始向右或向下移动,请计算阿福从 (1,1) 到达 (H,W) 的总路径数,由于答案可能很大,请将结果对 10 9 +7 取模
时间: 2024-02-04 16:01:59 浏览: 108
这是一个典型的动态规划问题,我们可以用一个二维数组 `dp` 来存储从起点 `(1,1)` 到每个位置的路径数。具体地,`dp[i][j]` 表示从起点 `(1,1)` 到 `(i,j)` 的路径数,初始时,`dp[1][1] = 1`。
接下来我们考虑如何计算 `dp[i][j]`。由于阿福只能向下或向右移动,因此他只能从 `(i-1,j)` 或 `(i,j-1)` 两个位置到达 `(i,j)`。如果 `(i,j)` 是一面墙,则路径数为 0。
因此我们可以得到状态转移方程:
```
if a[i][j] == '#':
dp[i][j] = 0
else:
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
```
最终,`dp[H][W]` 就是从起点 `(1,1)` 到终点 `(H,W)` 的总路径数。
下面是 Python 代码实现:
```python
h, w = map(int, input().split())
a = [input() for _ in range(h)]
dp = [[0] * (w+1) for _ in range(h+1)]
dp[1][1] = 1
for i in range(1, h+1):
for j in range(1, w+1):
if a[i-1][j-1] == '#':
dp[i][j] = 0
else:
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
print(dp[h][w])
```
这段代码首先读入矩阵的行数 `h` 和列数 `w`,然后用一个列表 `a` 存储矩阵的内容。接下来初始化一个二维数组 `dp`,将 `dp[1][1]` 的值设为 1。使用两个嵌套循环,计算每个 `dp[i][j]` 的值,并根据 `a[i][j]` 的值来判断当前位置是否为墙。最后输出 `dp[h][w]` 即可。
阅读全文