DFS走迷宫类问题

4.1 基础迷宫模板

class MazeSolver {
private:
    // 方向数组
    const int dx[4] = {-1, 1, 0, 0};  // 上下左右
    const int dy[4] = {0, 0, -1, 1};
    int rows, cols;
    vector<vector<int>> maze;
    vector<vector<bool>> visited;
    vector<pair<int,int>> path;
    
    bool isValid(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && 
               maze[x][y] == 0 && !visited[x][y];
    }
    
    bool dfs(int x, int y, int endX, int endY) {
        // 到达终点
        if (x == endX && y == endY) {
            path.push_back({x, y});
            return true;
        }
        
        // 标记当前位置
        visited[x][y] = true;
        path.push_back({x, y});
        
        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if (isValid(nextX, nextY)) {
                if (dfs(nextX, nextY, endX, endY))
                    return true;
            }
        }
        
        // 回溯
        path.pop_back();
        return false;
    }
    
public:
    MazeSolver(vector<vector<int>>& m) : maze(m) {
        rows = maze.size();
        cols = maze[0].size();
        visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
    }
    
    vector<pair<int,int>> findPath(int startX, int startY, 
                                  int endX, int endY) {
        path.clear();
        if (dfs(startX, startY, endX, endY))
            return path;
        return vector<pair<int,int>>();
    }
};

4.2 字母矩阵模板

class WordSearcher {
private:
    const int dx[8] = {-1,-1,-1,0,0,1,1,1};  // 8个方向
    const int dy[8] = {-1,0,1,-1,1,-1,0,1};
    int rows, cols;
    vector<vector<char>> board;
    vector<vector<bool>> visited;
    
    bool isValid(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y];
    }
    
    bool dfs(int x, int y, const string& word, int index) {
        // 找到完整单词
        if (index == word.length()) return true;
        
        // 当前字符不匹配
        if (board[x][y] != word[index]) return false;
        
        // 标记当前位置
        visited[x][y] = true;
        
        // 尝试八个方向
        for (int i = 0; i < 8; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if (isValid(nextX, nextY)) {
                if (dfs(nextX, nextY, word, index + 1))
                    return true;
            }
        }
        
        // 回溯
        visited[x][y] = false;
        return false;
    }
    
public:
    WordSearcher(vector<vector<char>>& b) : board(b) {
        rows = board.size();
        cols = board[0].size();
        visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
    }
    
    bool exist(string word) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0]) {
                    if (dfs(i, j, word, 0))
                        return true;
                }
            }
        }
        return false;
    }
};

6.1 迷宫寻路

问题描述：在N×M的迷宫中找到从起点到终点的路径，0表示通道，1表示墙壁。

思路分析：

1. 使用DFS遍历所有可能路径
2. 记录已访问位置避免循环
3. 维护当前路径信息
4. 找到任意一条可行路径即可

6.2 单词搜索

问题描述：在字母矩阵中搜索是否存在给定的单词，可以上下左右四个方向移动。

思路分析：

1. 从每个可能的起点开始DFS
2. 按字母顺序匹配单词
3. 标记已访问位置
4. 找到完整单词则返回true

6.3 骑士巡游

问题描述：在N×N的棋盘上，骑士从给定起点出发，访问每个格子恰好一次。

思路分析：

1. 使用DFS尝试所有可能的移动序列
2. 记录已访问的格子
3. 使用Warnsdorff启发式优化
4. 当访问所有格子时完成巡游

7. 总结

• DFS是解决走迷宫类问题的有效方法
• 理解不同类型问题的特点和解决策略
• 掌握优化技巧，提高搜索效率
• 灵活运用模板代码，解决实际问题
• 通过练习题目加深理解和应用能力