欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[算法]格子里的整数

程序员文章站 2024-03-16 18:41:52
...

格子里的整数

问题地址

题目描述

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
题目解析
  1. 给定一个格子,你在起始点,可以上下左右移动
  2. 问移动到最后一个点时的最小代价是多少
思路解析
  1. 因为本题可以向上和向左移动,所以动态规划无法解决这道题.但是这道题用动态规划可以碰巧AC
  2. 一种解法是使用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)
    
相关标签: 格子里的整数