考试的时候太紧张，思路有点混乱，下来又思考了下第二题，完成剩下的代码，用了简单的几个测试用例测了一下，各位大佬有兴趣可以相互讨论一下，错误欢迎指正。
因为刚才发的贴忘记发题目了，也有bug，吃过饭重新修改了一遍代码，重发一次
题目大概是走格子问题，一个n*m的矩阵格子，每个格子的值是路程（还是体力？反正一个意思），从最上一行任意格子走到最下一行任意格子，每次可以走上下左右四个方向，求从最上行走到最下一行的最短路程。代码是自己写的，可能有bug，目前测试了几个用例，暂时没发现问题
n,m = 5,5
matrix1 = [[1 ,20,20,20,20],
[1 ,1 ,1 ,1 ,1],
[20,20,20,20,1],
[1 ,1 ,1 ,1 ,1 ],
[1 ,20,20,20,20]]
matrix = [[1 ,1 ,1 ,1 ,1],
[1 ,20,20,20,20],
[1 ,1 ,1 ,1 ,1 ],
[20,20,20,20,1 ],
[20,20,20,20,1]]
matrix = [[1 ,1 ,2 ,2 ,1 ],
[1 ,10,0 ,20,1],
[20,20,20,0 ,20],
[20,1 ,8 ,9 ,20 ],
[1 ,1 ,2 ,2 ,1 ]]
n,m = 3,4
matrix = [[3 ,4 ,8 ,4 ],
[0 ,0 ,0 ,0 ],
[3 ,1 ,3 ,1 ]]
n,m = 4,3
matrix = [[3 ,4 ,8 ,4 ],
[0 ,0 ,0 ,0 ],
[3 ,1 ,3 ,1 ]]
every_result = []
for start in range(m):
dp = [[float('inf') for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
dp[i][start] = matrix[i][start]
elif i != 0 and j == 0:
dp[i][start] = dp[i-1][start] + matrix[i][start]
else:
if i == 0 and start+j<m:
dp[i][start+j] = dp[i][start+j-1] + matrix[i][start+j]
elif i != 0 and start+j<m and start+j+1<m:
dp[i][start+j] = min(dp[i][start+j-1],dp[i][start+j+1],dp[i-1][start+j]) + matrix[i][start+j]
elif i != 0 and start+j<m and start+j+1==m:
dp[i][start+j] = min(dp[i][start+j-1],dp[i-1][start+j]) + matrix[i][start+j]
if i == 0 and start-j>=0:
dp[i][start-j] = dp[i][start-(j-1)] + matrix[i][start-j]
elif i != 0 and start-j>0:
dp[i][start-j] = min(dp[i][start-(j-1)],dp[i][start-(j-1)],dp[i-1][start-j]) + matrix[i][start-j]
elif i != 0 and start-j == 0:
dp[i][start-j] = min(dp[i][start-(j-1)],dp[i-1][start-j]) + matrix[i][start-j]
start = dp[i].index(min(dp[i]))
every_result.append(min(dp[n-1]))
result = min(every_result)
print(result)
全部评论
(4) 回帖