C语言迷宫求解算法输出异常，请求错误定位与修正

问题概述 #

编写了一个从(0,0)出发、以'G'为终点的迷宫求解算法，预期用'+'标记完整可行路径，但实际输出仅标记了前两个位置，删除第101行的return true后有进展但仍未得到正确结果。

预期与实际输出 #

预期输出 #

+  #  #  #  #  # 
 +  +  #  #  #  # 
 #  +  #  #  #  # 
 #  +  #  #  #  # 
 #  +  +  #  +  + 
 #  #  +  +  +  #

实际输出 #

+  #  #  #  #  # 
 +  #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  # 

代码错误分析 #

1. 布尔值判断错误：solveMazeUtil返回bool类型，但代码中用== '.'判断递归结果，属于类型不匹配的逻辑错误，应判断是否为true。
2. 代码块缺少大括号：每个方向尝试的if分支包含多行语句，但未用{}包裹，导致return true会无条件执行，直接打断递归逻辑。
3. 冗余的路径标记：递归调用后手动标记sol和修改maze完全多余，递归函数内部会自行处理路径标记与回溯，这会导致路径标记混乱。
4. 函数原型缺失：mazeGo函数在main调用前未声明原型，编译会产生警告，可能引发未定义行为。
5. 回溯逻辑失效：错误的条件判断导致函数提前返回，回溯（取消路径标记）的逻辑从未被触发。

修复后的完整代码 #

#include <stdio.h>
 
// Maze size
#define N 6

//define boolean
#ifndef MYBOOLEAN_H
#define MYBOOLEAN_H

#define false 0
#define true 1
typedef int bool;
#endif

int startX = 0;
int startY = 0;

//function prototypes
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N]);
bool mazeGo(char maze[N][N]);
void printSolution(char sol[N][N]);

int main()
{
    char maze[N][N] = {{'.','#','#','#','#','#'},
                       {'.','.','.','.','.','#'},
                       {'#','.','#','#','#','#'},
                       {'#','.','#','#','#','#'},
                       {'.','.','.','#','.','G'},
                       {'#','#','.','.','.','#'}};
 
    mazeGo(maze);
    return 0;
}

//print the solution
void printSolution(char sol[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %c ", sol[i][j]);
        printf("\n");
    }
}
 
//checking if in correct path
bool isSafe(char maze[N][N], int x, int y)
{
    // 允许终点'G'通过判断，配合后续的终点检查
    if (x >= 0 && x < N && y >= 0 && y < N && (maze[x][y] == '.' || maze[x][y] == 'G'))
        return true;
    else
        return false;
}
 
bool mazeGo(char maze[N][N])
{
    char sol[N][N] = {{'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'}};
 
    if (solveMazeUtil(maze, startX, startY, sol) == false) {
        printf("No solution");
        return false;
    }
 
    printSolution(sol);
    return true;
}
 
//actual maze solving
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N])
{
    // if (x, y) is goal return true
    if (maze[x][y] == 'G') {
        sol[x][y] = '+';
        return true;
    }
 
    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y) == true) {
        // mark x, y as part of solution path
        sol[x][y] = '+';
        // 标记当前位置为已访问，避免重复走
        char temp = maze[x][y];
        maze[x][y] = '#'; 
        
        // 尝试四个方向：右、下、左、上（可调整顺序）
        if (solveMazeUtil(maze, x + 1, y, sol) == true)
            return true;
        if (solveMazeUtil(maze, x, y + 1, sol) == true)
            return true;
        if (solveMazeUtil(maze, x - 1, y, sol) == true)
            return true;
        if (solveMazeUtil(maze, x, y - 1, sol) == true)
            return true;    
        
        // 回溯：当前位置不是路径的一部分，取消标记
        sol[x][y] = '#';
        maze[x][y] = temp; 
    }
    return false;
}

修复说明 #

1. 修正递归结果的判断逻辑，将== '.'改为== true。
2. 移除递归调用后冗余的sol标记和maze修改，改用临时变量保存原迷宫值，回溯时恢复，避免破坏非路径点。
3. 补充所有函数的原型声明，解决编译警告。
4. 修改isSafe函数，允许终点'G'通过判断，确保递归能到达终点位置。
5. 调整回溯逻辑的触发时机，确保路径探索失败时能正确取消当前位置的标记。

运行修复后的代码，即可得到预期的完整路径标记输出。

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