登录
  • #刷题

求助‌‌‌‌‌‌‍‍‌‍‍‌‌‍‌‍‌‍‍‌‌‍‍‌‍‌‍‌‌‍‌‍一道路径的问题

darrenchou8155
1097
31
给一个 n*n 的方格, 从左上起点到右下终点,返回出一条起点到终点的路径(可以不一定是最短),如果没有的话那么就返回None,

每个小格子上面有一个数字,移动的时候只能往小于等于自己的格子走,可以上下左右移动。

input:

grid1 = [[4,3,5],

[2,3,3],

[2,2,1]

]

output:

[4,3,3,2,1] 或者 [4,2,2,2,1][4,3,3,2,2,,2,1]

我用bfs 写的无法返回这样的结果,请教下大家怎么写这个题的代码,我可以学习下。希望大家发个正确的代码,谢谢啦

下面是我写的,但是结果不太对,感觉是把上面答案给混合了。

## (0,0) is source, (n-1, n-1) is target[br][/br][br][/br]import collections[br][/br][br][/br]def findPath(grid):[br][/br][br][/br]	n = len(grid)[br][/br][br][/br]	seen = set()[br][/br][br][/br]	dirs = [(-1,0), (1,0), (0,1), (0,-1)][br][/br][br][/br]	res = [][br][br][/br]	queue = collections.deque()[br][/br][br][/br]	queue.append((0,0))[br][/br][br][/br]	res.append(grid[0][0])[br][/br][br][/br]	while queue:[br][/br][br][/br]		i,j = queue.popleft()[br][/br][br][/br]		for x,y in dirs:[br][/br][br][/br]			new_i = x + i[br][/br][br][/br]			new_j = y + j[br][/br][br][/br]			if new_i<0 or new_i>=n or new_j<0 or new_j>=n or grid[new_i][new_j] > grid[i][j]:[br][/br][br][/br]				continue[br][/br][br][/br]			if (new_i, new_j) in seen:[br][/br][br][/br]				continue[br][/br][br][/br]			# print((new_i,new_j))[br][/br][br][/br]			# print(grid[new_i][new_j])[br][/br][br][/br]			res.append(grid[new_i][new_j])[br][/br][br][/br]			if new_i==n-1 and new_j == n-1:[br][/br][br][/br]				return res[br][/br][br][/br]			seen.add((new_i, new_j))[br][/br][br][/br]			queue.append((new_i, new_j))[br][/br][br][/br]	return None[/i]
31条回复
热度排序

发表回复