c - C迷宫求解算法

Question

基本上，我试图用C语言实现一个算法，它可以用右手或左手的规则来求解迷宫。我在一个文件里看到一个像这样的三角形迷宫：
我已经实现了解析文件并将迷宫加载到动态2d数组中的函数。根据数组中的值，我可以判断每个字段是否有右边框、左边框和垂直边框（根据字段的位置，上边框或下边框）我也被告知起始点的坐标（即，在这个特定例子中的6，1）和跟随的初始边界（即底部），当然，是否使用右手或左手规则来找到出口。
我应该列出通向出口的字段的坐标。我基本上已经实现了所有必要的函数来解析和检查迷宫的有效性，但是我并不完全理解如何在算法中使用右手和左手规则。我希望这是足够的信息，以了解我正在努力做什么。我不一定需要特定的代码，我只需要了解如何实际进行这项工作。
谢谢。

Answer 1

让我们用三角形迷宫细胞来表述右手法则。假设我们通过穿过单元格的底边进入单元格，如下图中的灰色箭头所示。
右手规则告诉我们要把右手放在墙上当我们进入牢房时，墙在哪里？
在上面的第一个例子中，右边没有墙。我们右边一定有堵墙，所以我们想一直向右拐，直到撞到它为止。在三角形迷宫中右转意味着顺时针旋转60度，跨过三角形的边缘进入相邻的细胞。
在第二种情况下，当我们进入牢房的时候，右边就有一面墙。我们想让这堵墙保持在我们的右边，所以我们向左拐，朝着那个方向走到相邻的牢房。
在第三种情况下，两边都有墙我们必须转身离开牢房我们将通过反向移动返回到上一个单元格，所以右边的墙这次将是三角形的另一条边。
为了遵循左边的规则，我们在上图的镜像上使用类似的推理。
接下来，我们需要网格单元的数值表示。有多种方法可以对单元格和边进行编号。一种可能性如下图所示。每个三角形的边编号为0、1、2左边是三角形的两个方向，显示每个方向的边编号中间是每个三角形方向的八种可能的墙配置右边是每个墙配置的十进制和二进制表示，使用边号从右到左索引二进制数字，即从最低有效数字到最高有效数字。
使用这个编号方案，问题中显示的迷宫可以用以下文本表示。第一行包含网格中的行数和列数第二行描述了我们的起点：行号、列号、交叉边其余行包含单元格描述。

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语言索引数组的方式。例如，我们会说左上角的单元格在row 0和column 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。第二个索引是我们要穿过的边的编号，使用我们要离开的三角形的边编号。第三个索引用于查找上面列出的三条信息。
0:行号的更改。
1:列号的变化。
2:我们刚过的边号，用新三角形的边号。
例如，让我们看看样本迷宫中的第一步。我们从row 5、column 0开始。总和奇偶性是 1，表示一个向上的三角形。我们越过了边缘因此，我们看 0。结果信息是 maze[1][0]，告诉我们在新的单元格中：
行索引更改 {0, 1, 2}。
列索引更改为 0。
我们刚越过边缘。
现在我们可以在一个循环中应用该算法，一旦我们离开迷宫的边界，这个循环就结束了。
下面是我所讨论的概念的ansi c实现。你必须调整它以适应你用来表示迷宫的任何文件格式。请记住，在开始位置的描述中，my format指定了进入迷宫的交叉边。

#include <stdlib.h>
#include <stdio.h>

int **maze, row_num, col_num,
    moves[2][3][3] = {   /* moves[orientation][edge] == {dr, dc, crossed} */
        { {-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"); /* We've left the maze. */
      return;
    }                    /* Increment the indices for external display. */
    printf("%d %d\n", r+1, c+1);
    edge = crossed;      /* We'll consider the crossed edge last. */
    while (1) {          /* Turn and look for an open edge. */
      edge = (edge+turn+3)%3;
      if ((maze[r][c] & (1 << edge)) == 0) {
        break;
      } 
    } 
    move = moves[(r+c)%2][edge];
    r += move[0];        /* After looking up the move, update the */
    c += move[1];        /*  cell position and the edge number. */
    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;             /* We decrement the cell indices because */
  --c_start;             /*  they are zero-based internally. */
  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;
}