我正在编写一个 MIPS 程序，该程序使用左手法则算法解决随机生成的迷宫问题。我正在尝试找到一种方法来跟踪迷宫中完成 LHR 算法时的最佳路径。
在程序中，$t9 是一个 32 位数字，用于存储正在穿越迷宫的汽车的当前位置和方向。第 31-24 位以 8 位 2C 数字存储行位置，第 23-16 位存储列位置。我已经想出了如何隔离行号和列号，并且我知道如何将它们存储到 .data 空间中的单词数组中，但我不确定我将如何找到哪些空间已经存在已访问，也就是数组中的重复值。
到目前为止，当它完成迷宫时，数组看起来像这样:
0001020110 [从 0,0 开始，到 0,1，到 0,2，到 0,1，然后到 1,0]，我需要找到一种方法将它复制到一个新数组中，或者基本上清除 0,1，因为它访问了该空间两次并使其成为 000210。
或者，我可以将行和列拆分为两个单独的数组。非常感谢任何帮助。
这是目前算法的代码。我只包含了我的主要功能，因为描述的其他功能只链接到移动汽车的功能，而不是改变汽车的位置。
.data
rows: .space 100
cols: .space 100
location: .space 100
.text
la $a0, location
jal _leftHandRule
j endProgram
_leftHandRule:
#a0: address of location space
.text
goForward:
addi $t8, $zero, 1
andi $t4, $t9, 0x80000 #if the value in 0x80000 (bit 19, row 8) is not 0, then the car is in row 8, and has finished the maze
#row
srl $t5, $t9, 24
andi $t6, $t5, 0xff
sw $t6, location($t7)
addi $t7, $t7, 1 #increments t7 in as the array location counter
#column
srl $t5, $t9, 16
andi $t6, $t5, 0xff
sw $t6, location($t7)
addi $t7, $t7, 1 #increments t7 for the next loop
bne $t4, $zero, endLeftHandRule
andi $t0, $t9, 0x08
bne $t0, $zero, hitWall #if the value in 0x08 is not zero, there is a wall in front of the car
andi $t2, $t9, 0x04
beq $t2, $zero, noLeftWall #if the value in 0x04 is zero, there is no left wall beside the car
j goForward
最佳答案
我不会在位置流中寻找重复的坐标对，因为那是 O(N)(其中 N 是路径长度)。
我会在算法开始时将 MxN 位 visited 数组初始化为零(M，N = 列/行的最大迷宫大小)(因此数组大小为 M*N/8 字节，或者当使用整个字节而不是位时，则为 M*N 字节)。
然后当您访问特定的 [x,y] 位置时，您将 visited 中的相应位/字节设置为 1，例如 visited[y*N + x] = 1.
要测试您是否已经到过某个位置，请查看 visited[y*N + x] 值。这是 O(1) 测试。
最后，如果你的迷宫定义已经是 M*N，并且每个单元格中都有一些空闲的未使用位，你可以修改它，你可以使用那个而不是单独的数组(从问题上看并不明显，如何定义了迷宫，但是代码中有一些神奇的东西，比如单独的前墙/左墙，所以也许可以将这个已访问的位塞进去)。
如果你可以在 LHR 期间破坏迷宫定义，你也可以在其中添加假墙以标记你已经尝试过的方式(所以一旦你前进，你将在你身后的原始位置创建“前进”墙，防止LHR 下次“前进”，当它访问原始位置时，它现在会看到路线被阻塞)。
实际上我不确定这些信息如何帮助通过 LHR 算法创建最佳路径，我花了 5 秒的时间思考，我需要其他东西，可能包含递归，所以我会通过返回来了解访问过的单元格到特定的递归深度。再说一次，这样写对堆栈来说会是巨大的压力，所以我会选择数组，并且可能会从 LHR 更改为一些广域优先搜索，因为 LHR 有点深度优先，这不是最优的.. .所以我已经离开了你的道路。将我的回答仅作为描述如何将特定单元格标记为已访问，您将如何使用它取决于您。
再考虑 5 秒。您实际上可能真的很想在您的“位置”输出中找到特定的第一次访问单元格，以覆盖返回到它的盲目分支。
你可以通过读取从开始到 $t7 的“位置”数据来做到这一点，当你找到当前行/列的两个字节时，在它之后重置 t7，否则当到达 t7 时，它“未找到”(所以对于您在“位置”数据中执行 O(N) 搜索的每一步。
但我仍然会使用另一个“迷宫”数组，这次不仅存储“已访问”标志，还存储“下一个方向”。在 LHR 期间简单地覆盖它而不进行任何测试(每个 LHR 步骤 O(1)“测试”)。
到达迷宫尽头后，我会回到起点，沿着“下一步的方向”，生成带有坐标的“位置”数据。它将遵循 LHR 路径从开始到结束，没有死胡同分支(因为只有特定单元格的最后一个“下一个方向”将保留，从而导致退出。
关于algorithm - 在 MIPS 中查找字数组中的重复整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40383984/