网站导航
> 技术文档 > dfs刷题矩阵搜索问题

dfs刷题矩阵搜索问题

网友: 技术文档 2025-07-30 12:06:46

文章目录

  • N皇后
  • 有效的数独
    • 题解
    • 代码
  • 独解数
    • 题解
    • 代码
  • 单词搜索
    • 题解
    • 代码
  • 黄金矿工
    • 题解
    • 代码
  • 不同路径
    • 题解
    • 代码
  • 总结

N皇后

题目链接
dfs刷题矩阵搜索问题

题解

1. 画出决策树
2. 全局变量：ret用来统计结果，path统计每次的路径，checkcol检查行有没有Q，checkdig1检查主对角线有没有Q，checkdig2检查副对角线有没有Q
3. 剪枝：使用哈希表的策略，每一行不需要检查，每次都递归每一行该放的不会出现攻击，主对角线斜率一样，利用y-x = b，每一条线上截距是相同的，如果出现相同的就表明放过了Q，y-x可能为负数所以加上了n，副对角线y + x = b，和主对角线类似
4. 回溯：将列，主对角线和副对角线变为false，path[row][col]恢复为点
5. 递归出口：行越界的时候填完矩阵
dfs刷题矩阵搜索问题
dfs刷题矩阵搜索问题

代码

class Solution {public: // 检查列,主对角线和副对角线 // 行每次都只放一个不用检查,不会出现攻击 bool checkcol[10],checkdig1[20],checkdig2[20]; vector<vector<string>> ret; vector<string> path; int n; vector<vector<string>> solveNQueens(int _n) { n = _n; path.resize(n); for(int i = 0;i < n;i++) { path[i].append(n,\'.\'); } dfs(0); return ret; } void dfs(int row) { if(n == row) { ret.push_back(path); return; } for(int col = 0;col < n;col++)// 放置每一行 { if(!checkcol[col] && !checkdig1[row + col] && !checkdig2[col-row+n]) { path[row][col] = \'Q\'; checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = true; dfs(row+1); // 恢复现场 checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = false; path[row][col] = \'.\'; } } }};

有效的数独

题目链接
dfs刷题矩阵搜索问题

题解

1. 算法原理：去遍历这个数独，如果遇到了数字就判断这个数字是否在这一行，这一列，这一个方格中，如果不在就标记为true，如果在就直接返回false，说明出现了第二次了
2. bool checkrow[i][nums]：用来检查这一行是否存在nums这个数
bool checkcol[j][nums]：用来检查这一列是否存在nums这个数
bool check[i/3][j/3][nums]：用来检查小方格中是否存在nums这个数，除3是把9 * 9的矩阵分为0，1，2下标的3*3的小方格，刚好第一个小方格中0，1，2下标的数除3都是0，第二，三个小方格也是如此
dfs刷题矩阵搜索问题

代码

class Solution {public: bool checkrow[9][10];// 检查行 bool checkcol[9][10];// 检查列 bool check[3][3][10];// 检查小方格 bool isValidSudoku(vector<vector<char>>& board) { for(int row = 0;row < 9;row++) { for(int col = 0;col < 9;col++) { if(board[row][col] != \'.\') {  int nums = board[row][col] - \'0\';  if(checkrow[row][nums] || checkcol[col][nums] || check[row/3][col/3][nums])  return false;  checkrow[row][nums] = checkcol[col][nums] = check[row/3][col/3][nums] = true; } } } return true; }};

独解数

题目链接
dfs刷题矩阵搜索问题

题解

1. 画出决策树
2. 全局变量：checkcol检查列是否存在相同的数，checkrow检查行是否存在相同的数，gird检查小方格是否存在相同的数
3. 剪枝：bool dfs(board)，如果这一行最终有一个格子填不了了，就返回false，不往后填了，返回到上一层去填正确的数
4. 回溯：填了的数bool变为false，然后board恢复为点
5. 递归出口：函数走完填完所有的格子就结束了
6. 算法原理：这题主要考察三个返回，第一个返回，如果填完了dfs返回true了，就不需要填下一个i了，第二个返回，如果所有数都不满足，说明前面填错了，返回上一层重新填，第三个返回，如果所有有点的格子都填完了，并且没有错，就返回true

dfs刷题矩阵搜索问题

代码

class Solution {public: bool checkrow[9][10]; bool checkcol[9][10]; bool gird[3][3][10]; 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 nums = board[i][j] - \'0\';  checkcol[j][nums] = checkrow[i][nums] = gird[i/3][j/3][nums] = true; } } } dfs(board); } // 可以遍历所有空的位置的不需要row传参过来 bool dfs(vector<vector<char>>& nums) { for(int row = 0;row < 9;row++) { for(int col = 0;col < 9;col++) {  if(nums[row][col] == \'.\') {  for(char i = \'1\';i <= \'9\';i++)  { int data = i - \'0\'; if(!checkcol[col][data] && !checkrow[row][data] && !gird[row/3][col/3][data]) { nums[row][col] = i; checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = true; if(dfs(nums) == true) return true;// 如果这个位置填完了返回了true,就不要再试下一个i了 // 恢复现场 nums[row][col] = \'.\'; checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = false; }  }  // 可能出现填不了的情况,1到9都不行  return false; } } } // 空位置全都填完了,返回true return true; }};

单词搜索

题目链接
dfs刷题矩阵搜索问题

题解

1. 画出决策树
2. 全局变量：m，n矩阵的大小，vis数组标记这个格子已经走过了
3. 剪枝：如果找不到第一个匹配的字符就剪枝
4. 回溯：如果找不到下一个匹配的字符就回溯
5. 递归出口：pos是字符串的长度，如果匹配到越界就说明找到了
6. 函数头：i，j是匹配到第一个字符的坐标，s是字符串，pos是匹配的字符的位置，board是矩阵
7. 利用向量找i，j的上下左右，就不需要用四个for循环了
dfs刷题矩阵搜索问题dfs刷题矩阵搜索问题

代码

class Solution {public: int m,n; // 标记该点是否使用过了 bool vis[7][7]; 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; } // 上下左右四个坐标 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) { if(pos == word.size()) return true; for(int k = 0;k < 4;k++) { int x = i + dx[k],y = j + dy[k]; if(x >= 0 && x < m && y >= 0&&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; } } // 说明i,j位置找不到,是错误的位置 return false; }};

黄金矿工

题目链接
dfs刷题矩阵搜索问题

题解

1. 跟上一题非常类似，唯一要注意的是递归出口是可以每次更新的，因为写递归出口需要判断用for循环每次去更新比较麻烦
2. 可以使用path在参数中，dfs(path + gird[x][y])，这样每次加就不需要手动恢复现场了，函数会帮我们自动恢复现场，每次更新结果在dfs的开头，虽然多更新几次，但是不太麻烦
3. 我写的是全局的变量，需要恢复现场
dfs刷题矩阵搜索问题dfs刷题矩阵搜索问题

代码

class Solution {public: bool vis[16][16]; int m,n; int ret = 0; int ans; 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] != 0) {  // 避免重复使用这个位置  vis[i][j] = true;  ans += grid[i][j];  dfs(grid,i,j);  ret = max(ans,ret);  vis[i][j] = false;  ans -= grid[i][j]; } } } return ret; } int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; void dfs(vector<vector<int>>& grid,int i,int j) { for(int k = 0;k < 4;k++) { int x = dx[k] + i,y = dy[k] + j; if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]!= 0) { vis[x][y] = true; ans += grid[x][y]; dfs(grid,x,y); ret = max(ans,ret); vis[x][y] = false; ans -= grid[x][y]; } } }};

不同路径

题目链接
dfs刷题矩阵搜索问题

题解

1. 这题要注意的一点是设计一个全局变量count，用来统计0的个数，在参数中多一个step，如果step和count相同，并且这个点的值是2，那么就是一个路径
2. 这题和上题也非常相似
dfs刷题矩阵搜索问题

代码

class Solution {public: // 统计0的个数 int count; bool vis[21][21]; int m,n; int ans; int uniquePathsIII(vector<vector<int>>& grid) { // 初始化为局部变量了,符了 m = grid.size(),n = grid[0].size(); int dx,dy; for(int i = 0;i < m;i++) { for(int j = 0;j < n;j++) { if(grid[i][j] == 0) count++; else if(grid[i][j] == 1) {  dx = i;  dy = j;  } } }  grid[dx][dy] = true; dfs(grid,dx,dy,0); return ans; } int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; void dfs(vector<vector<int>>& grid,int i,int j,int step) { if(count == step && grid[i][j] == 2) { ans++; return; } for(int k = 0;k < 4;k++) { int x = dx[k] + i,y = dy[k] + j; if(x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 0) { vis[x][y] = true; dfs(grid,x,y,step + 1); vis[x][y] = false; } if(count == step&&x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 2) { vis[x][y] = true; dfs(grid,x,y,step); vis[x][y] = false; } } }};

总结

1. 题目识别什么时候用矩阵搜索？
当出现向上，向下，向左，向右搜索时可以使用
2. 怎么使用矩阵搜索？
上面的三题里做了，就是模版
3. 如果是矩阵填空的题怎么做，例如N皇后？
可以用bool数组标记填过的行列斜对角线检查是否有效，然后一层一层去搜索，这种题主要也是画决策树，就是多了几个bool数组检查使用过的格子，之后不再使用这个格子

网络标签：

相关问题