我在一次采访中被问到以下问题
给你一个 4 X 4 的网格。网格上的某些位置包含宝藏。您的任务是访问包含宝藏的所有位置并收集它。您可以在四个相邻的单元格（上、下、左、右）上移动。“宝藏”的每一个动作和动作都是单一的单位成本。您需要遍历整个网格，并收集网格上的所有宝藏，将所花费的成本降至最低。
如果我能正确回忆，这是给出的示例图：
U..X
..X.
X..X
..X.
其中，U是我现在的位置，X是宝物的位置。
我提出的解决方案是使用广度优先搜索遍历图并在这样做的同时“收集宝藏”。但是，面试官坚持认为有更好的方法可以将成本降到最低。我希望你能帮助我弄清楚。
您应该已经认识到这是一个小小的伪装的旅行推销员问题。使用广度优先，您可以确定您必须访问的不同顶点之间的最短路径，从而为您提供一个派生图，其中仅包含这些路径作为顶点之间的加权边。从那时起，它就是经典的 TSP。
单独的 BFS 无法为您解决问题，因为您无法同时向各个方向移动。这不是单一来源的最短路径问题，因为一旦你收集到宝藏，你就会从当前位置开始通往下一个的路径，而不是从原来的位置开始。
收集所有宝藏所需的时间取决于您访问箱子的顺序X。由于只有五个，您可以尝试所有 120 个排序，计算成本，然后选择最好的一个。
请注意，如果顺序是固定的，则解决方案很简单：您按顺序将单元格之间的曼哈顿距离相加，然后选择最小的结果。