C语言递归回溯法生成迷宫边界路径异常问题排查与解决

问题说明 #

使用递归回溯法编写C语言迷宫生成程序，要求四周边界全部为墙体（值为1），仅起点为路径（值为0），但打印结果中总有两处边界被当作路径。

原代码 #

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

#define MAX_SIZE 20

void generateMaze(int maze[MAX_SIZE][MAX_SIZE], int row, int col, int width, int height);
void printMaze(int maze[MAX_SIZE][MAX_SIZE], int width, int height);

int main() {
    int width = 20;  // Width of the maze
    int height = 20; // Height of the maze

    int maze[MAX_SIZE][MAX_SIZE];

    // Initialize maze with walls
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            maze[i][j] = 1;
        }
    }

    srand(time(NULL));  // Seed the random number generator

    generateMaze(maze, 1, 0, width, height);  // Generate the maze starting from position (0, 0)
    // start position must avoid the four corner
    
    printMaze(maze, width, height);           // Print the generated maze

    return 0;
}

void generateMaze(int maze[MAX_SIZE][MAX_SIZE], int row, int col, int width, int height) {
    int directions[4][2] = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}};  // Right, Down, Left, Up
    int shuffle[4] = {0, 1, 2, 3};

    // Shuffle the directions randomly
    for (int i = 3; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }

    // Mark the current cell as empty space
    maze[row][col] = 0;

    for (int i = 0; i < 4; i++) {
        int dx = directions[shuffle[i]][0];
        int dy = directions[shuffle[i]][1];
        int newRow = row + dy;  // Neighbor row
        int newCol = col + dx;  // Neighbor column
        int midRow = row + dy / 2;  // Midpoint row
        int midCol = col + dx / 2;  // Midpoint column

        // Check if the neighbour coordinates are within the maze boundaries
        if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width && maze[newRow][newCol] == 1) {
            // Carve a path between the current cell and the neighbour
            maze[midRow][midCol] = 0;
            generateMaze(maze, newRow, newCol, width, height);  // Recursively generate the maze from the neighbor cell
        }
    }
}

void printMaze(int maze[MAX_SIZE][MAX_SIZE], int width, int height) {
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (maze[i][j] == 1) {
                printf("# ");  // Print wall
            } else {
                printf("  ");  // Print empty space
            }
        }
        printf("\n");
    }
}

原输出 #

# # # # # # # # # # # # # # # # # # # # 
  #           #                       # 
  #   # # #   #   # # # # # # #   # # # 
  #   #       #   #           #       # 
  # # #   # # #   #   # # #   # # #   # 
      #   #       #   #           #   # 
# #   #   #   # # # # #   # # #   #   # 
  #   #       #           #       #   # 
  #   # # #   # # #   # # #   # # #   # 
  #       #           #       #       # 
  # # #   # # # # # # #   # # #   #   # 
      #           #       #   #   #   # 
  #   # # # # #   # # #   #   #   # # # 
  #           #       #       #       # 
  # # # # # # # # #   # # # # # # #   # 
                  #   #       #       # 
  # # # # #   # # #   #   #   #   #   # 
      #       #       #   #   #   #   # 
# #   #   # # #   # # #   #   #   #   # 
      #                   #       #   # 

问题根源与修复方案 #

1. 起点位置错误 #

原代码中起点设置为(1, 0)，其中col=0属于左边界（第0列），直接将边界单元格设为路径（0），违反了边界全为墙体的要求。
修复：将起点改为内部单元格，比如(1, 1)，确保起点不在边界上：

generateMaze(maze, 1, 1, width, height);

2. 边界检查逻辑不严谨 #

原代码中递归时的边界判断允许访问边界区域（newRow >=0、newRow < height等），导致递归过程中可能修改边界单元格为路径。
修复：限制递归仅在内部区域进行，边界（第0行、最后一行、第0列、最后一列）禁止修改，修改判断条件：

if (newRow >= 1 && newRow < height-1 && newCol >= 1 && newCol < width-1 && maze[newRow][newCol] == 1)

3. 方向数组定义错误 #

原方向数组directions的元素与注释（Right, Down, Left, Up）不匹配，导致移动逻辑混乱，可能误触边界。正确的方向应该是：

• Right：列+2（dx=2, dy=0）
• Down：行+2（dx=0, dy=2）
• Left：列-2（dx=-2, dy=0）
• Up：行-2（dx=0, dy=-2）
  修复：修正方向数组定义：

int directions[4][2] = {{2, 0}, {0, 2}, {-2, 0}, {0, -2}};  // Right, Down, Left, Up

修复后的完整代码 #

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

#define MAX_SIZE 20

void generateMaze(int maze[MAX_SIZE][MAX_SIZE], int row, int col, int width, int height);
void printMaze(int maze[MAX_SIZE][MAX_SIZE], int width, int height);

int main() {
    int width = 20;
    int height = 20;

    int maze[MAX_SIZE][MAX_SIZE];

    // Initialize all cells as walls
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            maze[i][j] = 1;
        }
    }

    srand(time(NULL));

    // Start from inner cell (1,1) to avoid boundaries
    generateMaze(maze, 1, 1, width, height);
    
    printMaze(maze, width, height);

    return 0;
}

void generateMaze(int maze[MAX_SIZE][MAX_SIZE], int row, int col, int width, int height) {
    // Correct direction definition: [dx, dy] -> Right, Down, Left, Up
    int directions[4][2] = {{2, 0}, {0, 2}, {-2, 0}, {0, -2}};
    int shuffle[4] = {0, 1, 2, 3};

    // Shuffle directions for randomness
    for (int i = 3; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }

    // Mark current cell as path
    maze[row][col] = 0;

    for (int i = 0; i < 4; i++) {
        int dx = directions[shuffle[i]][0];
        int dy = directions[shuffle[i]][1];
        int newRow = row + dy;
        int newCol = col + dx;
        int midRow = row + dy / 2;
        int midCol = col + dx / 2;

        // Ensure new position is within inner area (not touching boundaries)
        if (newRow >= 1 && newRow < height-1 && newCol >= 1 && newCol < width-1 && maze[newRow][newCol] == 1) {
            // Carve path between current and new cell
            maze[midRow][midCol] = 0;
            generateMaze(maze, newRow, newCol, width, height);
        }
    }
}

void printMaze(int maze[MAX_SIZE][MAX_SIZE], int width, int height) {
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            printf(maze[i][j] == 1 ? "# " : "  ");
        }
        printf("\n");
    }
}

修复后效果 #

四周边界会保持完整的墙体，仅起点和内部生成的路径为空白，符合需求。

内容的提问来源于stack exchange，提问作者fpkt123