c++ - 船上有数字的最短路径

Question

我的家庭作业 (C++) 遇到了问题。我不是要完整的解决方案，但向正确的方向倾斜可能会有所帮助。 :)

我有一个 NxN 板(最大 N = 100)和该板上的一个 1x2 图形(立方体)。立方体的一侧涂成红色，另一侧涂成蓝色。立方体的默认位置是棋盘的左上角，蓝色面朝上:

B B . .
. . . .
. . . .
. . . .

(4x4例子，B代表蓝色)

黑板上可能有石头(障碍物)我可以用我的身材做出的 Action :

• 顺时针旋转 90/180/270 度
• 你可以围绕它的右/左/上/下边缘翻转立方体，改变它的“向上颜色”

例如，在默认位置使用右翻:

. . R R
. . . .
. . . .
. . . .

然后使用旋转 90:

. . R .
. . R .
. . . .
. . . .

然后使用左翻:

. B . .
. B . .
. . . .
. . . .

当然，旋转或翻转时，不能落在石头上。所以，问题是 - 对于任何给定的棋盘配置(图形位置和石头位置)编写一个程序，将“将立方体带回家”到默认位置(蓝色面朝上!)使用最少的数量移动，如果可能则返回 1，如果不可能则返回 0。

我觉得这个问题很有趣，但我不得不承认我对此有点困惑。特别是蓝边/红边部分。我真的不知道如何用通常的最短路径算法的语言来“翻译”那些我可以使用的 Action (而且我从未使用过任何这些算法)。因此，我将不胜感激您能提供的每一条建议! :)

Answer 1

首先，由于要求您找到确切的最佳路径，我会选择 Dijksta's algorithm .

对于此算法，您需要:

1. 一个给出下一个的函数可能的举动。
2. 告诉你一个位置是否已经存在的函数参观了。
3. 一个函数，告诉您每条路径的总成本。
4. 当然还有一个功能，它会在您进入决赛时告诉您职位

给定一个初始位置，您的立方体可以恰好到达 7 个新位置。很容易选择哪些是可能的。

G 只是您到目前为止所做的移动数 + 1 用于下一步 :)

我会使用哈希表来跟踪访问过的位置。 (这可能是最难写的函数)，但你现在不需要考虑太多。一个简单的 vector 和逐项比较就可以了。您可以在代码运行后对其进行优化。

最后，您需要检查立方体是否处于其初始位置蓝色面朝上。