让我们把右手定则转化为三角形迷宫单元格的术语。假设我们通过穿过下边进入单元格,如下图中的灰色箭头所示。
![Right-hand rule](https://istack.dev59.com/QErLr.webp)
右手定则告诉我们要把右手放在墙上。当我们进入一个单元格时,墙在哪里呢?
在上面的第一种情况中,没有紧挨着右边的墙。我们必须右转直到碰到墙为止。在三角形迷宫中右转意味着向顺时针方向旋转60度并越过三角形的边缘进入相邻的单元格。
在第二种情况中,我们进入单元格时右侧有一堵墙。我们想让这堵墙保持在右边,所以我们左转并向那个方向上的相邻单元格前进。
在第三种情况下,两侧都有墙。我们必须掉头离开单元格。我们通过沿着相反的方向移动返回上一个单元格,因此这次右侧的墙将是三角形的另一条边。
要遵循左手定则,我们在上述插图的镜像上使用类似的推理。
接下来,我们需要一个网格单元的数字表示。有多种方法可以对单元格和边进行编号。下面的图示显示了一种可能性。每个三角形的边都编号为0、1、2。左侧是三角形的两个方向,显示了每个方向的边编号。中间是每个三角形方向的八种可能的墙配置。右侧是每个墙配置的十进制和二进制表示,使用从右到左的边数索引二进制数字,即从最低有效数字到最高有效数字。
![Edge numbering and wall configurations](https://istack.dev59.com/iqjOq.webp)
使用这种编号方案,问题中显示的迷宫可以用以下文本表示。第一行包含网格中的行列数。第二行描述我们的起点:行号、列号、穿过的边缘。其余的行包含单元格描述。
6 7
6 1 2
4 2 1 1 5 0 3
4 1 2 0 2 0 1
4 0 1 0 1 3 4
4 2 7 4 0 1 1
6 4 1 1 6 4 2
2 2 6 0 2 2 6
最终实现的一部分是一个转移矩阵,它允许我们在迷宫遍历中查找下一个状态,给定当前状态和我们正在穿过的边。
在描述转移矩阵之前,让我很清楚地说明如何为网格编号。外部上,我们将从一开始对行和列进行编号,如图所示。这是我们读取起始位置和向用户显示解决方案的方式。但是,在程序内部,方便起见,从零开始对行和列进行编号,因为这是C语言索引数组的方式。例如,我们将说左上角的单元格位于第0
行和第0
列。这意味着如果我们有一个名为maze
的二维整数数组,则将称上部左侧单元格为maze [0] [0]
。
给定三角形网格单元格的行索引r
和列索引c
,使用基于零的编号,让我们根据r
和c
的奇偶性确定三角形方向。如果它们具有相同的奇偶性,即它们都是奇数或者都是偶数,则三角形朝下。否则,它指向上。实现这个的一种简单方法是通过计算(r+c)%2
,它在奇偶性相同时为0
,在奇偶性不同时为1
。
接下来,我们必须考虑我们要穿过的边。如果我们知道要离开的三角形的方向和要穿过的边的编号,我们可以计算出:
我们正在进入的三角形的行号。
我们正在进入的三角形的列号。
在新进入的三角形的上下文中,我们穿过的边的编号。
所有这些信息都表示在以下三维数组中。
moves[2][3][3] = {
{ {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} },
{ {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } };
第一个索引是用于表示三角形的方向,0
表示朝下的三角形,1
表示朝上的三角形。第二个索引是我们要穿越的边的编号,使用离开的三角形的边编号。第三个索引用于查找上面列出的三个信息。
例如,让我们看一下样例迷宫中的第一步。我们从第 5
行,第 0
列开始。总奇偶性为 1
,表示朝上的三角形。我们要穿过边 0
。因此,我们查看 maze[1][0]
。得到的信息是 {0, 1, 2}
,告诉我们在新单元格中:
行索引不变。
列索引增加 1
。
我们刚刚穿过的边是 2
。
现在,我们可以应用该算法,以循环的方式运行直到我们离开迷宫边界。
下面是一个 ANSI C 实现示例。您需要将其适应于用于表示迷宫的任何文件格式,请记住,在起始位置的描述中,我的格式指定了穿过哪条边进入迷宫。
#include <stdlib.h>
#include <stdio.h>
int **maze, row_num, col_num,
moves[2][3][3] = {
{ {-1, 0, 1}, {0, 1, 2}, {0, -1, 0} },
{ {0, 1, 2}, {1, 0, 0}, {0, -1, 1} } };
void go(int r, int c, int crossed, int turn) {
int edge, *move;
while (1) {
if (r < 0 || r >= row_num || c < 0 || c >= col_num) {
printf("out\n\n");
return;
}
printf("%d %d\n", r+1, c+1);
edge = crossed;
while (1) {
edge = (edge+turn+3)%3;
if ((maze[r][c] & (1 << edge)) == 0) {
break;
}
}
move = moves[(r+c)%2][edge];
r += move[0];
c += move[1];
crossed = move[2];
}
}
int main() {
int r_start, c_start, crossed_start, r, c;
scanf("%d %d", &row_num, &col_num);
scanf("%d %d %d", &r_start, &c_start, &crossed_start);
--r_start;
--c_start;
maze = (int **) malloc(row_num*sizeof(int *));
for (r = 0; r < row_num; ++r) {
maze[r] = (int *) malloc(col_num*sizeof(int));
for (c = 0; c < col_num; ++c) {
scanf("%d", &maze[r][c]);
}
}
printf("\nRight-hand rule:\n");
go(r_start, c_start, crossed_start, -1);
printf("Left-hand rule:\n");
go(r_start, c_start, crossed_start, 1);
return 0;
}