文章目录
有效的数独
递归解法思路
- 将每个数独的格子视为一个任务，依次检查每个格子是否合法。
如果当前格子中的数字违反了数独规则（在行、列或 3×3 小方块中重复），直接返回 False。
递归检查下一个格子，直到所有格子都检查完毕。
如果所有格子都合法，则返回 True。
class Solution
{
// 使用三个布尔数组分别记录数独中行、列和3x3小方块中是否已经存在某个数字。
bool row[9][10]; // row[i][num] 表示第 i 行是否已经存在数字 num
bool col[9][10]; // col[j][num] 表示第 j 列是否已经存在数字 num
bool 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;
}
}
}
// 如果遍历结束没有发现冲突，说明数独有效，返回 true
return true;
}
};
解数独
思路：回溯算法
- 使用回溯法填充数独的空格。
对于每个空格，尝试填入数字 1-9，并检查当前数字是否满足数独规则：
当前数字在行中是否唯一。
当前数字在列中是否唯一。
当前数字在 3×3 小方块中是否唯一。
如果满足规则，则递归求解下一个空格；如果不满足，则回溯到上一步继续尝试。
当所有空格都填满且数独有效时，返回结果。
class Solution
{
// 使用三个布尔数组记录数独中行、列和3x3小方块中是否已经存在某个数字
bool col[9][10]; // col[j][num] 表示第 j 列是否已经存在数字 num
bool row[9][10]; // row[i][num] 表示第 i 行是否已经存在数字 num
bool grid[3][3][10]; // grid[i][j][num] 表示第 (i, j) 个 3x3 小方块中是否已经存在数字 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 / 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 到 9
for(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 都无法填入，返回 false
return false;
}
}
}
// 如果遍历完所有格子都有效，返回 true
return true;
}
};
单词搜索
思路：回溯+深度优先搜索 (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)
{
// 递归终止条件：如果已经匹配到单词的最后一个字符，返回 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 搜索：
当前点的黄金加入总和。
标记当前点已访问，递归搜索四个方向。
搜索完成后，恢复当前点状态（回溯）。
返回所有路径中黄金总和的最大值。
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。
搜索完成后，恢复当前点状态（回溯）。
返回所有满足条件的路径总数。
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; // 回溯时恢复状态
}
}
}
};