来了来了，大P家Karat的宝藏问题第三题蟒蛇解法

看了网上这么多人遇到这道题。也有说是旅行商问

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有问题欢迎指出！

Code after revised

1. def Find_Treasrue(checkboard, src, dst):
   
2.     visited = set()
   
3.     Best_path = {}
   
4.     Best_path['path'] = []
   
5.     Best_path['len'] = [len(checkboard) * len(checkboard[0]) + 1]
   
6.     Path = []
   
7. 
   
8.     global cur_treasure
   
9.     cur_treasure = 0
   
10.     total_treasure = 0
    
11. 
    
12.     for i in xrange(len(checkboard)):
    
13.         for j in xrange(len(checkboard[0])):
    
14.             if checkboard[i][j] == 1:
    
15.                 total_treasure += 1
    
16. 
    
17.     def DFS(src):
    
18.         global cur_treasure
    
19.         if len(Path) + 1 >= Best_path['len']: #
    
20.             return
    
21.         else:
    
22.             # forward pass
    
23.             Path.append(src)
    
24.             visited.add(src)
    
25.             if checkboard[src[0]][src[1]] == 1:
    
26.                 cur_treasure += 1
    
27.             if src == dst:
    
28.                 if cur_treasure == total_treasure:
    
29.                         Best_path['len'] = len(Path)
    
30.                         Best_path['path'] = Path[:]
    
31.                 return
    
32. 
    
33.             for step in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
    
34.                 x, y = src[0] + step[0], src[1] + step[1]
    
35.                 if 0 <= x < len(checkboard) and 0 <= y < len(checkboard[0]) and checkboard[x][y] >= 0 and (x, y) not in visited:
    
36.                     DFS((x, y))
    
37. 
    
38.             # backward pass
    
39.             if checkboard[src[0]][src[1]] == 1:
    
40.                 cur_treasure -= 1
    
41.             visited.remove(src)
    
42.             Path.pop()
    
43. 
    
44.     DFS(src)
    
45.     return Best_path

复制代码

这题可不可以三维BFS解？多的一维来记录当前有多少个 treasure 了？

keith.collens 发表于 2018-12-30 10:56
这题可不可以三维BFS解？多的一维来记录当前有多少个 treasure 了？

不确定，需要具体记录每一条路径访问过哪些treasure，好像不太现实

这个路径不是最短