C++递归回溯迷宫求解问题：全路径被标记而非仅解路径

Hey Spencer, let's figure out why every traversable spot in your maze is getting marked as @ instead of just the valid solution path. This is a super common pitfall with recursive maze solvers—you're missing the critical backtracking step!

The Root Cause #

When you recursively explore a path, you mark the current position as visited (@), but if that path turns out to be a dead end, you never undo that mark. So every spot your algorithm steps on gets permanently tagged, even if it's not part of the final solution.

The Fix: Add Backtracking to Undo Invalid Paths #

Here's the core logic your solver needs to follow, with the key backtracking step highlighted:

1. Check if the current position is the end point—if yes, return true (we found the path!).
2. Check if the current position is invalid (out of bounds, a wall, or already marked as visited)—if yes, return false.
3. Temporarily mark the current position as visited (@).
4. Recursively explore all four directions (up, down, left, right).
5. If none of the directions lead to the end, undo the mark (set it back to its original traversable value, like . or a space) before returning false.
6. If any direction leads to the end, keep the mark and return true.

Example Code Comparison #

Incorrect (No Backtracking)

This is probably what your current code looks like—notice how it never undoes the @ mark:

bool solveMaze(vector<vector<char>>& maze, int x, int y) {
    // Check if we've reached the end
    if (maze[x][y] == 'E') return true;
    // Check if current position is invalid
    if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] != '.') {
        return false;
    }
    // Mark as visited, but never undo it
    maze[x][y] = '@';
    // Explore directions
    return solveMaze(maze, x+1, y) || solveMaze(maze, x-1, y) || 
           solveMaze(maze, x, y+1) || solveMaze(maze, x, y-1);
}

Correct (With Backtracking)

Notice the added step to revert the mark if the path is a dead end:

bool solveMaze(vector<vector<char>>& maze, int x, int y) {
    // 1. Check if we've reached the end
    if (maze[x][y] == 'E') {
        return true;
    }
    // 2. Check if current position is invalid (walls, out of bounds, already visited)
    if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || 
        maze[x][y] == '#' || maze[x][y] == '@') {
        return false;
    }
    // 3. Save the original value (in case your start is 'S' instead of '.')
    char original = maze[x][y];
    // 4. Temporarily mark as visited
    maze[x][y] = '@';
    // 5. Explore all four directions
    bool foundPath = solveMaze(maze, x+1, y) || 
                     solveMaze(maze, x-1, y) || 
                     solveMaze(maze, x, y+1) || 
                     solveMaze(maze, x, y-1);
    // 6. BACKTRACK: If no path found, revert the mark
    if (!foundPath) {
        maze[x][y] = original;
    }
    // 7. Return whether we found a valid path from this position
    return foundPath;
}

Quick Additional Tips #

• Handle the Start Position: If your maze uses a special character like S for the start, make sure your valid check includes it (or replace it with . before starting the recursion).
• Avoid Rechecking Visited Spots: Your invalid check should explicitly skip positions marked @ to prevent infinite loops.
• Match Your Maze's Symbols: Adjust the code to use your maze's actual wall character (like #) and traversable character (like . or space).

With this backtracking step added, only the positions that are part of the actual solution path will stay marked as @—all dead-end paths will be reverted to their original state.

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