-4

所以，我有这个问题。我有这个矩阵：

1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 0 T 0 1
H 0 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

我需要建立一条从 H 开始的路径，它的坐标为 (3.1) 到 T(2.8) 我需要：我需要一个读取矩阵 A[1..M,1..N] 的程序，它本身代表一个迷宫使用元素 [0,1] 并读取 H,T 值。值 1 被认为是一堵墙，你不能穿过它。所以我之前发布了这个问题，我需要一些语法帮助。

我在伪代码中的看法是这样的：

var walkingDirection = up;
var walkingDirection1 = down;
var walkingDirection2 = right;
var walkingDirection3 = left;
while (not at T)
    if (next field in walkingDirection is not 1)
        go to next field in walkingDirection
    else if
       (next field in walkingDirection1 is not 1)
        go to next field in walkingDirection1
else if
       (next field in walkingDirection2 is not 1)
        go to next field in walkingDirection2
else if
         (next field in walkingDirection3 is not 1)
        go to next field in walkingDirection3
    end if
end while

请帮我一些语法

int myArray[5][10] = { {1 1 1 1 1 1 1 1 1 1},
                       {1 1 0 0 0 1 0 T 0 1},
                       {H 0 0 1 1 1 0 1 1 1},
                       {1 1 0 0 0 0 0 0 0 1},
                       {1 1 1 1 1 1 1 1 1 1} };
int H = myArray [3][1];
int T = myArray [2][8];

if myArray [a+1][b]==1)
4

1 回答 1

3

不幸的是，您的算法不适用于任何类型的可解迷宫。

仔细查看您计划执行的不同阶段的逐步级别，您会发现能够验证它甚至不适用于给出的示例迷宫。

要看到这一点，最好通过示例来播放整个算法。

1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 0 T 0 1
H 0 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

从节点开始H：

  • 首先检查while条件：

    我们不在节点T，所以循环将运行。

  • 检查 walkDirection 我们看到有一个1，所以这个分支不能被采用。

  • 对于walkingDirection1 也是如此，所以这个分支也不能被取走。

    相反，算法将进入的walkingDirection2 分支向右迈出一步。

  • 由于我们已经访问了walkingDirection2 分支，因此不再检查walkingDirection3。

  • 控制流到达 while 循环的末尾。

    我们必须再次检查条件：仍然不在 node T，所以我们必须继续。

    ……

继续以这种方式逐步播放示例，您很快就会发现问题所在。就是下图中标有的那一行*：

1 1 1 1 1 1 1 1 1 1
1 1 * 0 0 1 0 T 0 1
H 0 * 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

一旦你的算法进入地牢的那个部分，它就会不断地上下走动。

  • 在仍然可以向上走的时候走 walkDirection 分支。

  • 在 walkDirection1 中迈出一步 walkDirection 被阻止在下一次运行中转身，因为现在 walkDirection 再次可以步行。

... 那么该怎么办？

虽然只测试任何可能的方向通常不是一个坏主意——事实上，除了测试并希望最好——你的算法缺少某种记忆。

为了防止它循环运行，它必须能够检测到它已经检查了该选项，或者更好地“记住”有趣的点。那些提供尚未经过测试的可能性。

虽然不是最有效的版本，但一个非常简单的想法可能是保留已检查的所有字段的列表。为已经访问过的每个字段保留记录，例如：该字段位于某某位置，而我从某某字段来到那里，您将防止一遍又一遍地犯同样的错误。

保留您能够检查的所有潜在候选人的第二份列表，因为您已经在旁边输入了一个字段，记住以下内容：当我站在某某字段上时，我看到了某某字段那个时候你应该能够继续检查最有趣的领域。

大纲

总结到目前为止给出的想法，该算法可以归结为两个函数：

下一个字段（）

从您目前看到的字段列表中取出一个字段。

如果它已经被检查过，就丢弃它，因为再次检查它没有任何价值。继续丢弃检查过的字段，直到：

  • 你的清单是空的：那么迷宫没有解决方案

    你可以退出程序然后。

  • 你会发现一个直到现在还没有被检查过的字段。

    在这种情况下检查（）它。

.

检查字段（）

检查您是否已经在节点T

  • 如果是的话 - 当你刚刚设法逃离地牢时，大声唱“万岁”。

    哦，是的 - 你可以在这里退出你的程序。

  • 如果不

    在您的检查字段列表中输入一条新记录，记住您来自哪里。

    检查所有相邻字段是否可以到达并且是否已经检查过。

    • 如果它们可以访问但尚未检查，请务必将它们添加到到目前为止看到的有趣字段列表中，记住您从哪个字段看到它们。

      现在继续next_field()

.

这样，一旦程序启动，您唯一要做的就是检查 ()字段H并等待结果。

... 也可以看看

为了获得更高的赌注，您可能需要查看以下任何材料：

于 2013-03-27T08:22:47.010 回答