鲍勃和爱丽丝合作参加了一个游戏节目。在赢得第一轮比赛后，他们现在可以进入一个藏有金币的迷宫。如果鲍勃能收集到所有的金币，并把它们送到爱丽丝的位置，他们就能分到金币。鲍勃可以水平或垂直移动，只要他停留在迷宫中，并且单元格没有被阻挡。迷宫由一个n x m的数组来表示。每个单元格都有一个值，其中0是开放的，1是阻塞的，2是开放的，有一个金币。鲍勃从(行，列)=(0，0)的单元格的左上方开始。爱丽丝的位置由（x，y）给出。确定.最短的路径，鲍勃可以按照收集所有金币，并把它们交给爱丽丝。如果Bob不能收集并交给所有金币，返回-1。
约束：-
1<=n,m<=100
0<=金币数量<=10枚。
1 <=x < n
1 <=y < m
谁能帮我想出一个算法？
半强制算法在这里会很好，原因很简单，这个问题是NP-Hard。
为了证明这一点，我们需要做一些简化。将迷宫转移到一个图上，从每个硬币到另一个硬币的路径是一条加权边，硬币是节点。现在的问题是找到从Bob到所有节点的最短路径，并以任何顺序返回到Alice，按照 这个 Stack Overflow中的问题这是NP-Hard。
为此，给定的约束条件很低，所以就可以用蛮力。
我有一个蛮力算法的想法。
找出所有硬币对的最短路径... O(#coins * (E + V log V)) 使用Dijkstra算法多次。
创建所有硬币的所有排列组合。O(#coins!)，其中 ! 标志着因子号。
对于每个排列组合。
对于每两个连续的硬币，在组合中，
找出两枚硬币之间的最短路径（使用阶段1）。注意不要走到一个你不小心已经去过的硬币上。
(循环外)返回阶段3中路径之和最短的排列方式。
时间复杂度为 O(#coins! + #coins * (E + V log V)). 这是一个很大的，但考虑到你的限制是可能的!