在 MIPS 中查找字数组中的重复整数
Finding Duplicate Integers in Word Array in MIPS
我正在编写一个 MIPS 程序，使用左手法则算法解决随机生成的迷宫问题。我正在尝试找到一种方法来跟踪迷宫中完成 LHR 算法时的最佳路径。
在程序中，$t9是一个32位的数字，存储了穿越迷宫的小车的当前位置和方向。第 31-24 位以 8 位 2C 数字存储行位置，第 23-16 位存储列位置。我已经想出了如何隔离行号和列号，并且我知道如何将它们存储到 .data space 中的单词数组中，但我不确定如何找到哪个spaces 已经被访问过，也就是数组中的重复值。
到目前为止，当它完成迷宫时，数组看起来像这样：
0001020110 [从 0,0 开始，到 0,1，到 0,2，到 0,1，然后到 1,0]，我需要找到一种方法将其复制到新的数组，或者基本上清除 0,1，因为它访问了 space 两次并使其成为 000210。
或者，我可以将行和列拆分为两个单独的数组。非常感谢任何帮助。
这是目前算法的代码。我只包括了我的主要功能，因为其他功能仅 link 描述了移动汽车的功能，并且不改变汽车的位置。
.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 = columns/rows 的最大迷宫大小）（因此数组大小为 M*N/8 字节，或者当使用整个字节而不是位时，则为 M*N 字节）。
然后当您访问特定的 [x,y] 位置时，您将 visited 中对应的 bit/byte 设置为一个，例如 visited[y*N + x] = 1.
要测试您是否已经到过某个位置，请查看 visited[y*N + x] 值。那是 O(1) 测试。
最后，如果你的迷宫定义已经是 M*N，并且每个单元格中都有一些空闲的未使用位，你可以修改它，你可以使用那个而不是单独的数组（从问题上看并不明显，迷宫是如何定义的，但是代码中有一些魔力，比如单独的 front/left 墙，所以也许可以将这个已访问的位塞入其中。
如果你可以在 LHR 期间破坏迷宫定义，你也可以在其中添加假墙以标记你已经尝试过的方式（所以一旦你继续前进，你会在原来的后面创建 "forward" 墙位置，阻止 LHR 下次去"forward"，当它访问原始位置时，它现在会看到路线被阻塞）。
实际上我不确定这个信息如何帮助通过 LHR 算法创建最佳路径，我花了 5 秒的时间思考，我需要其他东西，可能包含递归，所以我会知道访问过的单元格通过返回特定的递归深度。再说一次，这样写对堆栈来说会是巨大的压力，所以我会选择数组，并且可能会从 LHR 更改为一些广域优先搜索，因为 LHR 有点深度优先，这不是最优的.. .所以我已经离开了你的道路。将我的回答仅作为描述如何将特定单元格标记为已访问，您将如何使用它取决于您。
再考虑5秒。你实际上可能真的想在你的 "location" 输出中找到那个特定的 cell 第一次访问，以覆盖返回它的盲分支。
你可以通过读取从开始到 $t7 的 "location" 数据来做到这一点，当你找到当前 row/column 的两个字节时，在它之后重置 t7，否则当达到 t7 时，它是"not found"（因此对于每个步骤，您都会在 "location" 数据中进行 O(N) 搜索）。
但我仍然会使用另一个 "maze" 数组，这次不仅存储 "visited" 标志，而且存储 "direction to next"。在 LHR 期间简单地覆盖它而无需任何测试（每个 LHR 步骤 O(1) "test"）。
到达迷宫尽头后，我会返回开始并跟随 "direction to next"，生成带坐标的 "location" 数据。它将遵循 LHR 路径从头到尾没有死胡同分支（因为只有特定单元格的最后 "direction of next" 会保留，这会导致退出。
我正在编写一个 MIPS 程序，使用左手法则算法解决随机生成的迷宫问题。我正在尝试找到一种方法来跟踪迷宫中完成 LHR 算法时的最佳路径。
在程序中，$t9是一个32位的数字，存储了穿越迷宫的小车的当前位置和方向。第 31-24 位以 8 位 2C 数字存储行位置，第 23-16 位存储列位置。我已经想出了如何隔离行号和列号，并且我知道如何将它们存储到 .data space 中的单词数组中，但我不确定如何找到哪个spaces 已经被访问过，也就是数组中的重复值。
到目前为止，当它完成迷宫时，数组看起来像这样：
0001020110 [从 0,0 开始，到 0,1，到 0,2，到 0,1，然后到 1,0]，我需要找到一种方法将其复制到新的数组，或者基本上清除 0,1，因为它访问了 space 两次并使其成为 000210。
或者，我可以将行和列拆分为两个单独的数组。非常感谢任何帮助。
这是目前算法的代码。我只包括了我的主要功能，因为其他功能仅 link 描述了移动汽车的功能，并且不改变汽车的位置。
.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 = columns/rows 的最大迷宫大小）（因此数组大小为 M*N/8 字节，或者当使用整个字节而不是位时，则为 M*N 字节）。
然后当您访问特定的 [x,y] 位置时，您将 visited 中对应的 bit/byte 设置为一个，例如 visited[y*N + x] = 1.
要测试您是否已经到过某个位置，请查看 visited[y*N + x] 值。那是 O(1) 测试。
最后，如果你的迷宫定义已经是 M*N，并且每个单元格中都有一些空闲的未使用位，你可以修改它，你可以使用那个而不是单独的数组（从问题上看并不明显，迷宫是如何定义的，但是代码中有一些魔力，比如单独的 front/left 墙，所以也许可以将这个已访问的位塞入其中。
如果你可以在 LHR 期间破坏迷宫定义，你也可以在其中添加假墙以标记你已经尝试过的方式（所以一旦你继续前进，你会在原来的后面创建 "forward" 墙位置，阻止 LHR 下次去"forward"，当它访问原始位置时，它现在会看到路线被阻塞）。
实际上我不确定这个信息如何帮助通过 LHR 算法创建最佳路径，我花了 5 秒的时间思考，我需要其他东西，可能包含递归，所以我会知道访问过的单元格通过返回特定的递归深度。再说一次，这样写对堆栈来说会是巨大的压力，所以我会选择数组，并且可能会从 LHR 更改为一些广域优先搜索，因为 LHR 有点深度优先，这不是最优的.. .所以我已经离开了你的道路。将我的回答仅作为描述如何将特定单元格标记为已访问，您将如何使用它取决于您。
再考虑5秒。你实际上可能真的想在你的 "location" 输出中找到那个特定的 cell 第一次访问，以覆盖返回它的盲分支。
你可以通过读取从开始到 $t7 的 "location" 数据来做到这一点，当你找到当前 row/column 的两个字节时，在它之后重置 t7，否则当达到 t7 时，它是"not found"（因此对于每个步骤，您都会在 "location" 数据中进行 O(N) 搜索）。
但我仍然会使用另一个 "maze" 数组，这次不仅存储 "visited" 标志，而且存储 "direction to next"。在 LHR 期间简单地覆盖它而无需任何测试（每个 LHR 步骤 O(1) "test"）。
到达迷宫尽头后，我会返回开始并跟随 "direction to next"，生成带坐标的 "location" 数据。它将遵循 LHR 路径从头到尾没有死胡同分支（因为只有特定单元格的最后 "direction of next" 会保留，这会导致退出。