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

文章目录

有效的数独
解数独
单词搜索
黄金矿工
不同的路径|||

leetcode.cn/problems/valid-sudoku/description/" rel="nofollow">有效的数独

在这里插入图片描述
递归解法思路

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

class Solution 
{// 使用三个布尔数组分别记录数独中行、列和3x3小方块中是否已经存在某个数字。bool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 numbool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 numbool grid[3][3][10]; // grid[i][j][num] 表示第 (i, j) 个 3x3 小方块中是否已经存在数字 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 是否已经在当前行、列或 3x3 小方块中存在if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num])return false; // 如果存在，说明数独无效，返回 false// 如果没有冲突，则将 num 标记为已存在row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}// 如果遍历结束没有发现冲突，说明数独有效，返回 truereturn true;}
};

leetcode.cn/problems/sudoku-solver/description/" rel="nofollow">解数独

在这里插入图片描述
思路：回溯算法

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

class Solution 
{// 使用三个布尔数组记录数独中行、列和3x3小方块中是否已经存在某个数字bool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 numbool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 numbool grid[3][3][10]; // grid[i][j][num] 表示第 (i, j) 个 3x3 小方块中是否已经存在数字 numpublic:// 主函数：解数独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 / 3][j / 3][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 到 9for(int num = 1; num <= 9; num++){// 如果当前数字 num 在对应的行、列和小方块中都未出现if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]){// 填入数字board[i][j] = '0' + num; // 将整数转换为字符// 标记当前数字在行、列和小方块中已存在row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;// 递归求解下一步if(dfs(board) == true) return true;// 如果递归返回 false，说明当前解不正确，需要回溯board[i][j] = '.'; // 恢复空格子row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; // 取消标记}}// 如果 1-9 都无法填入，返回 falsereturn false;}}}// 如果遍历完所有格子都有效，返回 truereturn true;}
};

leetcode.cn/problems/word-search/description/" rel="nofollow">单词搜索

在这里插入图片描述
思路：回溯+深度优先搜索 (DFS)

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

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){// 递归终止条件：如果已经匹配到单词的最后一个字符，返回 trueif(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}
};

leetcode.cn/problems/path-with-maximum-gold/description/" rel="nofollow">黄金矿工

在这里插入图片描述
思路：回溯+深度优先搜索 (DFS)

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

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; // 回溯时恢复状态}}}
};

leetcode.cn/problems/unique-paths-iii/description/" rel="nofollow">不同的路径|||

在这里插入图片描述
思路：回溯+深度优先搜索 (DFS)

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

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; // 包括起点和终点在内，总共需要经过的格子数// 从起点开始进行 DFSvis[bx][by] = true; // 标记起点为已访问dfs(grid, bx, by, 1); // 起点已访问，计数为 1return ret; // 返回有效路径的数量}// 深度优先搜索函数void dfs(vector<vector<int>>& grid, int i, int j, int count){// 如果当前格子是终点（值为 2）if(grid[i][j] == 2){// 如果路径经过了所有需要访问的格子if(count == step)ret++; // 计数器加 1return;}// 遍历当前格子的四个方向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; // 回溯时恢复状态}}}
};