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

有效的数独

递归解法思路

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

1. class Solution
2. {
3.     // 使用三个布尔数组分别记录数独中行、列和3x3小方块中是否已经存在某个数字。
4.     bool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 num
5.     bool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 num
6.     bool grid[3][3][10]; // grid[i][j][num] 表示第 (i, j) 个 3x3 小方块中是否已经存在数字 num
7. public:
8.     bool isValidSudoku(vector<vector<char>>& board)
9.     {
10.         // 遍历整个 9x9 的棋盘
11.         for(int i = 0; i < 9; i++) // 遍历每一行
12.         {
13.             for(int j = 0; j < 9; j++) // 遍历每一列
14.             {
15.                 // 如果当前格子不为空（即不是 '.'）
16.                 if(board[i][j] != '.')
17.                 {
18.                     int num = board[i][j] - '0'; // 将字符数字转换为整数
20.                     // 检查当前数字 num 是否已经在当前行、列或 3x3 小方块中存在
21.                     if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
22.                         return false; // 如果存在，说明数独无效，返回 false
24.                     // 如果没有冲突，则将 num 标记为已存在
25.                     row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
26.                 }
27.             }
28.         }
30.         // 如果遍历结束没有发现冲突，说明数独有效，返回 true
31.         return true;
32.     }
33. };

复制代码

解数独

思路：回溯算法

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

1. class Solution
2. {
3.     // 使用三个布尔数组记录数独中行、列和3x3小方块中是否已经存在某个数字
4.     bool col[9][10];    // col[j][num] 表示第 j 列是否已经存在数字 num
5.     bool row[9][10];    // row[i][num] 表示第 i 行是否已经存在数字 num
6.     bool grid[3][3][10]; // grid[i][j][num] 表示第 (i, j) 个 3x3 小方块中是否已经存在数字 num
8. public:
9.     // 主函数：解数独
10.     void solveSudoku(vector<vector<char>>& board)
11.     {
12.         // 初始化布尔数组，标记已存在的数字
13.         for(int i = 0; i < 9; i++) // 遍历每一行
14.         {
15.             for(int j = 0; j < 9; j++) // 遍历每一列
16.             {
17.                 if(board[i][j] != '.') // 如果当前格子有数字
18.                 {
19.                     int num = board[i][j] - '0'; // 将字符数字转换为整数
20.                     // 标记当前数字已经存在于对应的行、列和小方块中
21.                     row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
22.                 }
23.             }
24.         }
26.         // 递归进行数独求解
27.         dfs(board);
28.     }
30.     // 深度优先搜索 + 回溯
31.     bool dfs(vector<vector<char>>& board)
32.     {
33.         // 遍历整个数独棋盘
34.         for(int i = 0; i < 9; i++) // 遍历每一行
35.         {
36.             for(int j = 0; j < 9; j++) // 遍历每一列
37.             {
38.                 if(board[i][j] == '.') // 找到空格子
39.                 {
40.                     // 尝试填入数字 1 到 9
41.                     for(int num = 1; num <= 9; num++)
42.                     {
43.                         // 如果当前数字 num 在对应的行、列和小方块中都未出现
44.                         if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num])
45.                         {
46.                             // 填入数字
47.                             board[i][j] = '0' + num; // 将整数转换为字符
48.                             // 标记当前数字在行、列和小方块中已存在
49.                             row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
51.                             // 递归求解下一步
52.                             if(dfs(board) == true) return true;
54.                             // 如果递归返回 false，说明当前解不正确，需要回溯
55.                             board[i][j] = '.'; // 恢复空格子
56.                             row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; // 取消标记
57.                         }
58.                     }
59.                     // 如果 1-9 都无法填入，返回 false
60.                     return false;
61.                 }
62.             }
63.         }
65.         // 如果遍历完所有格子都有效，返回 true
66.         return true;
67.     }
68. };

复制代码

单词搜刮

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

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

1. class Solution
2. {
3.     bool vis[7][7]; // 标记每个网格点是否已被访问，避免重复使用
4.     int m, n;       // 网格的行数 (m) 和列数 (n)
6. public:
7.     // 主函数，判断单词是否存在
8.     bool exist(vector<vector<char>>& board, string word)
9.     {
10.         // 初始化网格大小
11.         m = board.size();
12.         n = board[0].size();
14.         // 遍历网格中的每一个字符，寻找与单词第一个字符匹配的位置作为起点
15.         for(int i = 0; i < m; i++)
16.         {
17.             for(int j = 0; j < n; j++)
18.             {
19.                 // 如果当前字符是单词的第一个字符
20.                 if(board[i][j] == word[0])
21.                 {
22.                     vis[i][j] = true; // 标记当前格子为已访问
23.                     // 从当前格子开始深度优先搜索
24.                     if(dfs(board, i, j, word, 1)) return true;
25.                     vis[i][j] = false; // 回溯时取消标记
26.                 }
27.             }
28.         }
29.         return false; // 如果所有起点都不能找到完整单词，则返回 false
30.     }
32.     // 方向数组，用于表示上下左右的移动
33.     int dx[4] = {0, 0, -1, 1}; // 水平方向
34.     int dy[4] = {-1, 1, 0, 0}; // 垂直方向
36.     // 深度优先搜索函数
37.     bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
38.     {
39.         // 递归终止条件：如果已经匹配到单词的最后一个字符，返回 true
40.         if(pos == word.size())
41.             return true;
43.         // 遍历当前格子的四个方向
44.         for(int k = 0; k < 4; k++)
45.         {
46.             int x = i + dx[k]; // 新的行坐标
47.             int y = j + dy[k]; // 新的列坐标
49.             // 判断新位置是否合法且匹配当前单词字符
50.             if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && board[x][y] == word[pos])
51.             {
52.                 vis[x][y] = true; // 标记新位置为已访问
53.                 // 递归继续搜索下一个字符
54.                 if(dfs(board, x, y, word, pos + 1)) return true;
55.                 vis[x][y] = false; // 回溯时取消标记
56.             }
57.         }
58.         return false; // 如果四个方向都找不到匹配路径，返回 false
59.     }
60. };

复制代码

黄金矿工

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

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

1. class Solution
2. {
3.     bool vis[16][16]; // 标记网格中的格子是否已被访问
4.     int m, n;         // 网格的行数 (m) 和列数 (n)
5.     int dx[4] = {0, 0, -1, 1}; // 表示移动的水平方向：左右
6.     int dy[4] = {-1, 1, 0, 0}; // 表示移动的垂直方向：上下
7.     int ret; // 记录黄金路径的最大总量
9. public:
10.     // 主函数，返回可以采集的最大黄金总量
11.     int getMaximumGold(vector<vector<int>>& grid)
12.     {
13.         m = grid.size();  // 获取网格的行数
14.         n = grid[0].size(); // 获取网格的列数
16.         // 遍历网格中的每一个格子
17.         for(int i = 0; i < m; i++)
18.         {
19.             for(int j = 0; j < n; j++)
20.             {
21.                 if(grid[i][j]) // 如果当前格子有黄金
22.                 {
23.                     vis[i][j] = true; // 标记当前格子为已访问
24.                     dfs(grid, i, j, grid[i][j]); // 从当前格子开始深度优先搜索
25.                     vis[i][j] = false; // 回溯时恢复状态
26.                 }
27.             }
28.         }
30.         return ret; // 返回找到的最大黄金总量
31.     }
33.     // 深度优先搜索函数
34.     void dfs(vector<vector<int>>& grid, int i, int j, int path)
35.     {
36.         ret = max(ret, path); // 更新最大黄金总量
38.         // 遍历四个方向
39.         for(int k = 0; k < 4; k++)
40.         {
41.             int x = i + dx[k]; // 计算新的行坐标
42.             int y = j + dy[k]; // 计算新的列坐标
44.             // 判断新坐标是否合法、是否未访问以及是否有黄金
45.             if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y] && grid[x][y])
46.             {
47.                 vis[x][y] = true; // 标记新位置为已访问
48.                 dfs(grid, x, y, grid[x][y] + path); // 递归搜索
49.                 vis[x][y] = false; // 回溯时恢复状态
50.             }
51.         }
52.     }
53. };

复制代码

不同的路径|||

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

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

1. class Solution
2. {
3.     int m, n, step; // m 和 n 是网格的行列大小，step 是需要经过的格子总数
4.     bool vis[21][21]; // 标记网格中的格子是否已被访问，避免重复访问
5.     int dx[4] = {0, 0, -1, 1}; // 表示水平方向的移动（左右）
6.     int dy[4] = {-1, 1, 0, 0}; // 表示垂直方向的移动（上下）
7.     int ret; // 记录所有满足条件的路径数
9. public:
10.     // 主函数：返回所有满足条件的路径数
11.     int uniquePathsIII(vector<vector<int>>& grid)
12.     {
13.         m = grid.size();  // 获取网格的行数
14.         n = grid[0].size(); // 获取网格的列数
15.         int bx = 0, by = 0; // 起点坐标
17.         // 遍历网格，初始化起点和统计需要经过的格子总数
18.         for(int i = 0; i < m; i++)
19.         {
20.             for(int j = 0; j < n; j++)
21.             {
22.                 if(grid[i][j] == 0) step++; // 统计值为 0 的空格
23.                 else if(grid[i][j] == 1)   // 找到起点
24.                 {
25.                     bx = i;
26.                     by = j;
27.                 }
28.             }
29.         }
30.         step += 2; // 包括起点和终点在内，总共需要经过的格子数
32.         // 从起点开始进行 DFS
33.         vis[bx][by] = true; // 标记起点为已访问
34.         dfs(grid, bx, by, 1); // 起点已访问，计数为 1
35.         return ret; // 返回有效路径的数量
36.     }
38.     // 深度优先搜索函数
39.     void dfs(vector<vector<int>>& grid, int i, int j, int count)
40.     {
41.         // 如果当前格子是终点（值为 2）
42.         if(grid[i][j] == 2)
43.         {
44.             // 如果路径经过了所有需要访问的格子
45.             if(count == step)
46.                 ret++; // 计数器加 1
47.             return;
48.         }
50.         // 遍历当前格子的四个方向
51.         for(int k = 0; k < 4; k++)
52.         {
53.             int x = i + dx[k]; // 新的行坐标
54.             int y = j + dy[k]; // 新的列坐标
56.             // 判断新位置是否合法
57.             if(x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != -1 && !vis[x][y])
58.             {
59.                 vis[x][y] = true; // 标记新位置为已访问
60.                 dfs(grid, x, y, count + 1); // 递归搜索下一步
61.                 vis[x][y] = false; // 回溯时恢复状态
62.             }
63.         }
64.     }
65. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。