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
思路
这道题没有限制只能向下和向右走，所以也可以往回走，就不能用动态规划，递进的方式求解。
考虑用深度优先的方法，
首先初始化一个距离数组mindis，大小和格子相同，代表从左上角起点，到每个位置花费的最小值。
从左上角（0，0）开始，深度优先访问其相邻的点，
假设当前位置是（x，y），检查（x，y）4个方向的点(x+1, y), (x-1, y), (x, y+1), (x, y-1)，
如果在格子内，且这个位置的距离misdis[i][j]大于mindis[x][y] + grid[x][y], 则更新misdis[i][j], 并继续深度遍历这个位置。
如图所示，cur表示到达(x, y)的花费，如果
- 检查(x+1, y),
cur + grid[x+1][y]表示到达右边格子的花费，如果这个值小于mindis[x+1][y]的话，就更新mindis[x+1][y]，并深度遍历(x+1, y) ->dfs(x+1, y, cur+grid[x+1][y]) - 检查(x-1, y)...
- 检查(x, y+1)...
- 检查(x, y-1)...
深度遍历的函数定义：
i表示横左边，j表示纵坐标，cur表示从左上角到达当前位置的花费。
function dfs(i, j, cur)
深度遍历结束后，我们就可以得到到达每个位置的最小花费了。
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))
