园区参观路径(100)
- 有一个矩形园区,从左上角走到右下角,只能向右、向下走;
- 共有多少条不同的参观路径;
输入描述:
第一行输入长度、宽度
后续每一行表示 对应位置是否可以参观,0可以,1不可以
输出描述:
不同路径的数量
示例1
输入:
3 3
0 0 0
0 1 0
0 0 0
输出:
2
示例2
输入:
4 3
0 1 0
0 0 0
0 0 1
1 0 0
输出:
2
思路:
- 深度优先,能走到终点,则max_path += 1
row, col = list(map(int, input().strip().split()))matrix = []
for i in range(row):matrix.append(list(map(int, input().strip().split())))# 两个方向
directs = [0, 1, 0]
max_paths = 0def dfs(x, y):global max_pathsd = 0while d < 2:xx = x + directs[d]yy = y + directs[d+1]if xx < row and yy < col and matrix[xx][yy] == 0: # 可以走 (位置可以重复参观)if xx == row - 1 and yy == col - 1:max_paths += 1returnelse:dfs(xx, yy)# 位置无效或者不能参观,则调转方向d += 1returndfs(0, 0)
print(max_paths)
- 动态规划
- matrix 表示格子数据
- dp 二维数组表示到达每个格子时的不同路径数,当第i行,第j列的格子即matrix[i-1][j-1]位置为0时,则可以从上边、左边走过来,对应的路径数为dp[i][j] = dp[i-1][j] + dp[i][j-1]
- 最后dp[row][col] 即为到达终点的不同路径数
from typing import Listdef func(matrix):global row, col# 第 i 行 j列 在dp中即为索引, 在matrix中 i-1, j-1 为索引# 二维数组 dp[i][j] 表示 matrix中从 (0, 0)起始点 到 (i - 1, j - 1)终点 的不同路径数,# 初始化均为 0dp: List[List[int]] = [[0 for _ in range(col+1)] for _ in range(row + 1)]# 为了将matrix[0][0] 起始点设置为 1 (起始点可以从上边、左边走过来)dp[0][1] = 1# 遍历当前要走到的格子下标 (i, j)for i in range(1, row + 1): # 要走的第i行 (i-1才为索引)for j in range(1, col + 1):# 如果当前格子为0,则可以从上边和左边走过来if matrix[i - 1][j - 1] == 0:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# dp[row][col] 就是从 (0, 0) 到 (m - 1, n - 1) 的不同路径数return dp[row][col]row, col = [int(x) for x in input().strip().split()]
matrix = []
for i in range(row):matrix.append([int(x) for x in input().strip().split()])print(func(matrix))