矩阵路径计数

1. 题目描述

给定一个 n×m 的矩阵，其中每个元素的值为 1 或 0。你需要从矩阵的左上角开始，找到一条路径到右下角。每次只能向右或向下移动，且路径经过的每个格子的值必须是 1。如果存在一条路径，输出路径的个数；如果没有路径，输出 0。

请你编写程序计算从左上角到右下角的所有可能路径数。

输入格式：

第一行包含两个整数 n 和 m，表示矩阵的行数和列数。

接下来 n 行，每行包含 m 个整数，表示矩阵的内容。每个整数为 0 或 1。

输出格式：

输出一个整数，表示从左上角到右下角的所有路径数。由于路径数可能非常大，请输出路径数对 (10^9+7) 取模的结果。

输入

3 3

1 1 1

0 1 1

1 1 1

输出

2

提示:

数据范围

对于 20% 数据，n,m≤10

对于 50% 数据，n,m≤50

对于 100% 数据，n,m≤100

2. 分析

这个题目是一个典型的回溯问题，要求在矩阵中寻找路径时进行分支限界，避免重复计算。我们可以用递归的方式从起点 (0, 0) 开始，不断地向右或向下走，直到到达终点 (n-1, m-1)。在每一步时，要判断当前格子是否可通行（即值为1），并在走到终点时返回成功路径。

为了优化计算，我们可以使用动态规划来减少重复计算。定义一个二维数组 dp[i][j] 表示从左上角 (0, 0) 到达位置 (i, j) 的路径数。递推关系如下：

如果当前格子 (i, j) 可通行（值为1），则可以从左边 (i, j-1) 或上方 (i-1, j) 走到当前格子。

边界条件：dp[0][0] = 1 表示起点有一条路径；对于第一行和第一列的格子，路径数只能由一个方向（上方或左方）到达。

最终，dp[n-1][m-1] 即为从起点到终点的路径数。

复杂度分析：

时间复杂度：O(n * m)，由于我们只遍历每个格子一次，时间复杂度为矩阵的大小。

空间复杂度：O(n * m)，用于存储动态规划数组。

3. 代码

MOD = 10**9 + 7

def countPaths(n, m, grid):
    # 初始化一个dp二维数组
    dp = [[0] * m for _ in range(n)]
    
    # 如果起点可通行，初始化dp[0][0]为1
    if grid[0][0] == 1:
        dp[0][0] = 1
    
    # 动态规划填充dp数组
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                if i > 0:
                    dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
                if j > 0:
                    dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD
    
    return dp[n-1][m-1]
    

# 输入处理
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

# 输出结果
print(countPaths(n, m, grid))