更衣室算法

Question

注:只是提醒一下，这不是我的学校的作业，因为我自己甚至不知道是哪个学校写的这个问题。希望没有发生误会。

我发现关于更衣室的这个有趣的问题：

裁判员的更衣室有N个储物柜，标有1，2，。。. N. 每个储物柜都是锁定的，但可以使用其独特的键打开。 每个储物柜钥匙的副本都在其相邻的储物柜中；也就是说，一份锁柜钥匙的副本放在储物柜I+1和I−1中(锁柜1的钥匙只在储物柜2，锁柜N的钥匙只在储物柜N−1中)。 网球在T个不同的储物柜里(你知道他们在哪个储物柜里)。给你钥匙M的储物柜和你的目标是收集所有的网球通过打开最少的储物柜。

对于图片，您可以直接看到它到这里的文件。

我必须给一些新生这个问题，但我想首先确保我自己已经有了正确的答案之前。

我想的是：

1. 需要一个接一个地检查球。因此，对于每个球(忽略其他球)，每个键必须通过遍历指定的球来访问。对于每个键，计算它访问球所采取的步骤。最小的结果存储在一个名为“总计步骤”的变量中。
2. 对下一个球做这件事，当我得到这个当前球的最小步数时。我将此值添加到“总步骤”中。
3. 特殊情况下，如果有一个球以上的键，然后键开始穿越从i+ 1和i-1。

我的问题是:我说得对吗？我不想和别人分享错误的算法，因为它是不专业的。期待收到任何意见、建议和投入。

Answer 1

您的算法不会产生最小的步骤数。你不能单独考虑球。让我们考虑以下情况:你只有一个锁柜号码1的钥匙，球在储物柜里-- 12，10，8，6，4，2。如果你按我给出的顺序考虑球，你的总步数将等于11 + 9 + 7 + 5 + 3 + 1，而你只需11步就能解决这个问题。您不应忽略前面步骤中访问的框。

Answer 2

下面是一种您可以使用的技巧：

将每个储物柜(其中有一个球，其中有一个键，而没有一个键)作为图中的一个节点。节点将分为两种类型：

A) Lockers having balls
B) Lockers of which you have keys.
C) Lockers which have none

考虑所有的储物柜类型-A是关闭的，类型-B是开放的.

从所有打开的储物柜中，找到通往所有封闭式储物柜的路径(从储物柜类型-B)，并以最小路径长度在A中打开储物柜。另外，打开属于这个最小路径的C型储物柜，并将它们从C类移到B类。

重复上面的步骤，直到A中所有的储物柜都打开。你遇到的所有最小路径长度之和将是你的答案。