【递归与回溯深度解析：经典题解精讲（下篇）】—— Leetcode

【递归与回溯深度解析：经典题解精讲（下篇）】—— Leetcode

有效的数独

递归解法思路

• 将每个数独的格子视为一个任务，依次检查每个格子是否合法。 如果当前格子中的数字违反了数独规则（在行、列或 × 小方块中重复），直接返回 False。 递归检查下一个格子，直到所有格子都检查完毕。 如果所有格子都合法，则返回 True。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    // 使用三个布尔数组分别记录数独中行、列和x小方块中是否已经存在某个数字。
    bool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 num
    bool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 num
    bool grid[][][10]; // grid[i][j][num] 表示第 (i, j) 个 x 小方块中是否已经存在数字 num
public:
    bool isValidSudoku(vector<vector<char>>& board) 
    {
        // 遍历整个 9x9 的棋盘
        for(int i = 0; i < 9; i++) // 遍历每一行
        {
            for(int j = 0; j < 9; j++) // 遍历每一列
            {
                // 如果当前格子不为空（即不是 '.'）
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0'; // 将字符数字转换为整数

                    // 检查当前数字 num 是否已经在当前行、列或 x 小方块中存在
                    if(row[i][num] || col[j][num] || grid[i / ][j / ][num])
                        return false; // 如果存在，说明数独无效，返回 false

                    // 如果没有冲突，则将 num 标记为已存在
                    row[i][num] = col[j][num] = grid[i / ][j / ][num] = true;
                }
            }
        }

        // 如果遍历结束没有发现冲突，说明数独有效，返回 true
        return true;
    }
};

解数独

思路：回溯算法

• 使用回溯法填充数独的空格。 对于每个空格，尝试填入数字 1-9，并检查当前数字是否满足数独规则： 当前数字在行中是否唯一。 当前数字在列中是否唯一。 当前数字在 × 小方块中是否唯一。 如果满足规则，则递归求解下一个空格；如果不满足，则回溯到上一步继续尝试。 当所有空格都填满且数独有效时，返回结果。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    // 使用三个布尔数组记录数独中行、列和x小方块中是否已经存在某个数字
    bool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 num
    bool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 num
    bool grid[][][10]; // grid[i][j][num] 表示第 (i, j) 个 x 小方块中是否已经存在数字 num

public:
    // 主函数：解数独
    void solveSudoku(vector<vector<char>>& board) 
    {
        // 初始化布尔数组，标记已存在的数字
        for(int i = 0; i < 9; i++) // 遍历每一行
        {
            for(int j = 0; j < 9; j++) // 遍历每一列
            {
                if(board[i][j] != '.') // 如果当前格子有数字
                {
                    int num = board[i][j] - '0'; // 将字符数字转换为整数
                    // 标记当前数字已经存在于对应的行、列和小方块中
                    row[i][num] = col[j][num] = grid[i / ][j / ][num] = true;
                }
            }
        }

        // 递归进行数独求解
        dfs(board);
    }

    // 深度优先搜索 + 回溯
    bool dfs(vector<vector<char>>& board)
    {
        // 遍历整个数独棋盘
        for(int i = 0; i < 9; i++) // 遍历每一行
        {
            for(int j = 0; j < 9; j++) // 遍历每一列
            {
                if(board[i][j] == '.') // 到空格子
                {
                    // 尝试填入数字 1 到 9
                    for(int num = 1; num <= 9; num++)
                    {
                        // 如果当前数字 num 在对应的行、列和小方块中都未出现
                        if(!row[i][num] && !col[j][num] && !grid[i / ][j / ][num])
                        {
                            // 填入数字
                            board[i][j] = '0' + num; // 将整数转换为字符
                            // 标记当前数字在行、列和小方块中已存在
                            row[i][num] = col[j][num] = grid[i / ][j / ][num] = true;

                            // 递归求解下一步
                            if(dfs(board) == true) return true;

                            // 如果递归返回 false，说明当前解不正确，需要回溯
                            board[i][j] = '.'; // 恢复空格子
                            row[i][num] = col[j][num] = grid[i / ][j / ][num] = false; // 取消标记
                        }
                    }
                    // 如果 1-9 都无法填入，返回 false
                    return false;
                }
            }
        }

        // 如果遍历完所有格子都有效，返回 true
        return true;
    }
};

单词搜索

思路：回溯+深度优先搜索 (DFS)

• 问题是查网格中是否存在给定单词。 遍历网格中的每个字符作为起点，使用回溯和 DFS 搜索路径： 如果当前字符匹配单词的第一个字符，则继续递归搜索四个方向（上下左右）。 使用标志位（例如临时修改字符）避免重复访问。 如果路径不符合要求，则回溯到上一层。 如果成功到完整路径，则返回 true；否则继续尝试其他起点。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    bool vis[7][7]; // 标记每个网格点是否已被访问，避免重复使用
    int m, n;       // 网格的行数 (m) 和列数 (n)

public:
    // 主函数，判断单词是否存在
    bool exist(vector<vector<char>>& board, string word) 
    {
        // 初始化网格大小
        m = board.size(); 
        n = board[0].size();

        // 遍历网格中的每一个字符，寻与单词第一个字符匹配的位置作为起点
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                // 如果当前字符是单词的第一个字符
                if(board[i][j] == word[0])
                {
                    vis[i][j] = true; // 标记当前格子为已访问
                    // 从当前格子开始深度优先搜索
                    if(dfs(board, i, j, word, 1)) return true;
                    vis[i][j] = false; // 回溯时取消标记
                }
            }
        }
        return false; // 如果所有起点都不能到完整单词，则返回 false
    }

    // 方向数组，用于表示上下左右的移动
    int dx[4] = {0, 0, -1, 1}; // 水平方向
    int dy[4] = {-1, 1, 0, 0}; // 垂直方向

    // 深度优先搜索函数
    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
    {
        // 递归终止条件：如果已经匹配到单词的最后一个字符，返回 true
        if(pos == word.size())
            return true;

        // 遍历当前格子的四个方向
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; // 新的行坐标
            int y = j + dy[k]; // 新的列坐标

            // 判断新位置是否合法且匹配当前单词字符
            if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && board[x][y] == word[pos])
            {
                vis[x][y] = true; // 标记新位置为已访问
                // 递归继续搜索下一个字符
                if(dfs(board, x, y, word, pos + 1)) return true;
                vis[x][y] = false; // 回溯时取消标记
            }
        }
        return false; // 如果四个方向都不到匹配路径，返回 false
    }
};

黄金矿工

思路：回溯+深度优先搜索 (DFS)

• 在网格中寻一条路径，使得采集的黄金总量最大，路径可以在上下左右四个方向移动，但不能重复访问。 遍历网格中的每个点作为起点，使用回溯和 DFS 搜索： 当前点的黄金加入总和。 标记当前点已访问，递归搜索四个方向。 搜索完成后，恢复当前点状态（回溯）。 返回所有路径中黄金总和的最大值。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    bool vis[16][16]; // 标记网格中的格子是否已被访问
    int m, n;         // 网格的行数 (m) 和列数 (n)
    int dx[4] = {0, 0, -1, 1}; // 表示移动的水平方向：左右
    int dy[4] = {-1, 1, 0, 0}; // 表示移动的垂直方向：上下
    int ret; // 记录黄金路径的最大总量

public:
    // 主函数，返回可以采集的最大黄金总量
    int getMaximumGold(vector<vector<int>>& grid) 
    {
        m = grid.size();  // 获取网格的行数
        n = grid[0].size(); // 获取网格的列数

        // 遍历网格中的每一个格子
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j]) // 如果当前格子有黄金
                {
                    vis[i][j] = true; // 标记当前格子为已访问
                    dfs(grid, i, j, grid[i][j]); // 从当前格子开始深度优先搜索
                    vis[i][j] = false; // 回溯时恢复状态
                }
            }
        }

        return ret; // 返回到的最大黄金总量
    }

    // 深度优先搜索函数
    void dfs(vector<vector<int>>& grid, int i, int j, int path)
    {
        ret = max(ret, path); // 更新最大黄金总量

        // 遍历四个方向
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; // 计算新的行坐标
            int y = j + dy[k]; // 计算新的列坐标

            // 判断新坐标是否合法、是否未访问以及是否有黄金
            if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && grid[x][y])
            {
                vis[x][y] = true; // 标记新位置为已访问
                dfs(grid, x, y, grid[x][y] + path); // 递归搜索
                vis[x][y] = false; // 回溯时恢复状态
            }
        }
    }
};

不同的路径|||

思路：回溯+深度优先搜索 (DFS)

• 在网格中寻一条路径，要求： 从起点走到终点。 必须经过所有空格，不能遗漏也不能重复。 使用回溯法遍历网格： 遍历网格到起点，并统计需要经过的空格数量。 从起点出发，递归搜索四个方向： 标记当前点已访问。 如果到达终点且已访问所有空格，路径计数+1。 搜索完成后，恢复当前点状态（回溯）。 返回所有满足条件的路径总数。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    int m, n, step; // m 和 n 是网格的行列大小，step 是需要经过的格子总数
    bool vis[21][21]; // 标记网格中的格子是否已被访问，避免重复访问
    int dx[4] = {0, 0, -1, 1}; // 表示水平方向的移动（左右）
    int dy[4] = {-1, 1, 0, 0}; // 表示垂直方向的移动（上下）
    int ret; // 记录所有满足条件的路径数

public:
    // 主函数：返回所有满足条件的路径数
    int uniquePathsIII(vector<vector<int>>& grid) 
    {
        m = grid.size();  // 获取网格的行数
        n = grid[0].size(); // 获取网格的列数
        int bx = 0, by = 0; // 起点坐标

        // 遍历网格，初始化起点和统计需要经过的格子总数
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 0) step++; // 统计值为 0 的空格
                else if(grid[i][j] == 1)   // 到起点
                {
                    bx = i;
                    by = j;
                }
            }
        }
        step += 2; // 包括起点和终点在内，总共需要经过的格子数

        // 从起点开始进行 DFS
        vis[bx][by] = true; // 标记起点为已访问
        dfs(grid, bx, by, 1); // 起点已访问，计数为 1
        return ret; // 返回有效路径的数量
    }

    // 深度优先搜索函数
    void dfs(vector<vector<int>>& grid, int i, int j, int count)
    {
        // 如果当前格子是终点（值为 2）
        if(grid[i][j] == 2)
        {
            // 如果路径经过了所有需要访问的格子
            if(count == step)
                ret++; // 计数器加 1
            return;
        }

        // 遍历当前格子的四个方向
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; // 新的行坐标
            int y = j + dy[k]; // 新的列坐标

            // 判断新位置是否合法
            if(x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != -1 && !vis[x][y])
            {
                vis[x][y] = true; // 标记新位置为已访问
                dfs(grid, x, y, count + 1); // 递归搜索下一步
                vis[x][y] = false; // 回溯时恢复状态
            }
        }
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-27，如有侵权请联系 cloudcommunity@tencent 删除前往查看遍历递归函数搜索leetcode