洛谷p1162c语言
时间: 2023-12-02 15:38:28 浏览: 28
这是一道经典的搜索题目,需要使用深度优先搜索(DFS)来解决。题目要求在一个矩阵中找到一条从左上角到右下角的路径,使得路径上的数字之和最小。我们可以从左上角开始,每次向右或向下移动一格,直到到达右下角。在移动的过程中,我们可以记录当前路径上的数字之和,并且每次只选择数字更小的方向进行移动。
具体实现时,我们可以使用一个二维数组dp[i][j]来记录从左上角到(i,j)位置的最小数字之和。初始时,dp等于矩阵中左上角的数字。然后我们从左到右、从上到下遍历矩阵,对于每个位置(i,j),我们可以通过dp[i-1][j]和dp[i][j-1]来更新dp[i][j],即:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
其中matrix[i][j]表示矩阵中第i行第j列的数字。最终,dp[n-1][m-1]就是从左上角到右下角的最小数字之和。
代码实现如下:
```python
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
# 初始化dp数组
dp = [[0] * m for _ in range(n)]
dp[0][0] = matrix[0][0]
# 更新dp数组
for i in range(1, n):
dp[i][0] = dp[i-1][0] + matrix[i][0]
for j in range(1, m):
dp[0][j] = dp[0][j-1] + matrix[0][j]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
print(dp[n-1][m-1])
```