[算法]格子里的整数
格子里的整数
题目描述
Description
Given a square grid of size n, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum.
Note : It is assumed that negative cost cycles do not exist in input matrix.
Input
The first line of input will contain number of test cases T. Then T test cases follow . Each test case contains 2 lines. The first line of each test case contains an integer n denoting the size of the grid. Next line of each test contains a single line containing N*N space separated integers depecting cost of respective cell from (0,0) to (n,n).
Constraints:1<=T<=50,1<= n<= 50
Output
For each test case output a single integer depecting the minimum cost to reach the destination.
Sample Input 1
2
5
31 100 65 12 18 10 13 47 157 6 100 113 174 11 33 88 124 41 20 140 99 32 111 41 20
2
42 93 7 14
Sample Output 1
327
63
题目解析
- 给定一个格子,你在起始点,可以上下左右移动
- 问移动到最后一个点时的最小代价是多少
思路解析
- 因为本题可以向上和向左移动,所以动态规划无法解决这道题.但是这道题用动态规划可以碰巧AC
- 一种解法是使用dijkstra
使用与前一个问题类似的动态规划是不可能解决这个问题的,因为这里的当前状态不仅依赖于右单元格和下单元格,而且还依赖于左单元格和上单元格。我们用dijkstra算法来解决这个问题。网格的每个单元代表一个顶点和相邻的顶点。我们不会从这些单元中生成一个明确的图,而是使用dijkstra算法中的矩阵。
图片和文字来自
如果使用动态规划就不会绕过157,而是从174那里走
代码实现
动态规划(原则上是不对的,但碰巧可以AC)
# 这道题 如果假设只能往右或者往下的话就很简单了
if __name__ == '__main__':
for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().strip().split(" ")))
matrix = [[0] * n for _ in range(n)]
k = 0
for i in range(n):
for j in range(n):
matrix[i][j] = arr[k]
k += 1
dp = [[0] * n for _ in range(n)]
dp[0][0] = matrix[0][0]
for i in range(1, n):
dp[i][0] = matrix[i][0] + dp[i - 1][0]
dp[0][i] = matrix[0][i] + dp[0][i - 1]
for i in range(1, n):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]
print(dp[-1][-1])
正确代码,我也没看懂
T = int(input())
for _ in range(T):
N = int(input())
arr = [int(x) for x in input().strip().split(' ')]
V = len(arr)
edge_list = []
for i in range(V):
if i%N != 0:
edge_list.append([(i, i-1), arr[i-1]])
if (i+1)%N != 0:
edge_list.append([(i, i+1), arr[i+1]])
if (i-N) >= 0:
edge_list.append([(i, i-N), arr[i-N]])
if (i+N) < (N*N):
edge_list.append([(i, i+N), arr[i+N]])
dist = dict()
dist[0] = arr[0]
par = dict()
par[0] = None
for i in range(1, V):
dist[i] = float('inf')
change = True
ite = 0
while ite < (V-1) and change:
change=False
for edge, wt in edge_list:
u = edge[0]
v = edge[1]
if dist[v] > (dist[u] + wt):
dist[v] = dist[u] + wt
par[v] = u
change = True
ite += 1
print(dist[V-1])
# Print the path to (N-1, N-1)
# node = V - 1
# while node is not None:
# print(node, end='<-')
# node = par[node]
# print(None)