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 Output1

327
63

思路

這道題沒(méi)有限制只能向下和向右走，所以也可以往回走，就不能用動(dòng)態(tài)規(guī)劃，遞進(jìn)的方式求解。

考慮用深度優(yōu)先的方法，

首先初始化一個(gè)距離數(shù)組mindis，大小和格子相同，代表從左上角起點(diǎn)，到每個(gè)位置花費(fèi)的最小值。

從左上角（0，0）開(kāi)始，深度優(yōu)先訪問(wèn)其相鄰的點(diǎn)，

假設(shè)當(dāng)前位置是（x，y），檢查（x，y）4個(gè)方向的點(diǎn)(x+1, y), (x-1, y), (x, y+1), (x, y-1)，

如果在格子內(nèi)，且這個(gè)位置的距離misdis[i][j]大于mindis[x][y] + grid[x][y], 則更新misdis[i][j], 并繼續(xù)深度遍歷這個(gè)位置。

如圖所示，cur表示到達(dá)(x, y)的花費(fèi)，如果

1. 檢查(x+1, y), cur + grid[x+1][y]表示到達(dá)右邊格子的花費(fèi)，如果這個(gè)值小于mindis[x+1][y]的話，就更新mindis[x+1][y]，并深度遍歷(x+1, y) -> dfs(x+1, y, cur+grid[x+1][y])
2. 檢查(x-1, y)...
3. 檢查(x, y+1)...
4. 檢查(x, y-1)...

深度遍歷的函數(shù)定義：

i表示橫左邊，j表示縱坐標(biāo)，cur表示從左上角到達(dá)當(dāng)前位置的花費(fèi)。

function dfs(i, j, cur)

深度遍歷結(jié)束后，我們就可以得到到達(dá)每個(gè)位置的最小花費(fèi)了。

python

def solve(grid):
    m, n = len(grid), len(grid[0])
    mindis = [[float('inf')]*n for _ in range(m)]
    def dfs(i, j, cur):
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if 0 <= x < m and 0 <= y < n and mindis[x][y] > cur + grid[x][y]:
                mindis[x][y] = cur + grid[x][y]
                dfs(x, y, cur + grid[x][y])
    dfs(0, 0, grid[0][0])
    return mindis[-1][-1]

for _ in range(int(input())):
    n = int(input())
    nums = list(map(int, input().split()))
    grid = [nums[i:i+n] for i in range(0, len(nums), n)]
    print(solve(grid))