devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

DFS：深搜+回溯+剪枝解决矩阵搜索问题

作者：从前慢现在也慢 | 2024-04-09 17:39:34

赞

踩

DFS：深搜+回溯+剪枝解决矩阵搜索问题

                                               创作不易，感谢三连！！ 

一、N皇后

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     vector<vector<string>> ret;
  4.     vector<string> path;
  5.     bool checkcol[9];
  6.     bool checkdig1[18];
  7.     bool checkdig2[18];
  8.     int n;
  9.     vector<vector<string>> solveNQueens(int _n) 
  10.     {
  11.         n=_n;
  12.         path.resize(n);
  13.         for(int i=0;i<n;++i)  path[i].append(n,'.');//先全部初始化成.
  14.          dfs(0);
  15.          return ret;
  16.     }
  17.  
  18.     void dfs(int row)
  19.     {
  20.         if(row==n) {ret.push_back(path);return;}
  21.         for(int col=0;col<n;++col)//枚举每一行的每个元素
  22.         {
  23.             if(checkcol[col]==false&&checkdig1[n+row-col]==false&&checkdig2[row+col]==false)//n+row-col防止越界
  24.             {
  25.                path[row][col]='Q';
  26.                checkcol[col]=checkdig1[n+row-col]=checkdig2[row+col]=true;
  27.                 dfs(row+1);
  28.                 //恢复现场
  29.                path[row][col]='.';
  30.                checkcol[col]=checkdig1[n+row-col]=checkdig2[row+col]=false;
  31.             }
  32.         }
  33.     }
  34. };

二、有效的数独

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     bool checkrow[9][10];
  4.     bool checkcol[9][10];
  5.     bool checkgrid[3][3][10];
  6.     bool isValidSudoku(vector<vector<char>>& board) 
  7.     {
  8.          for(int row=0;row<9;++row)
  9.          {
  10.             for(int col=0;col<9;++col)
  11.             {
  12.                 if(board[row][col]!='.')
  13.                 {
  14.                     int num=board[row][col]-'0';
  15.                     if(checkrow[row][num]||checkcol[col][num]||checkgrid[row/3][col/3][num]) return false;
  16.                     checkrow[row][num]=checkcol[col][num]=checkgrid[row/3][col/3][num]=true;
  17.                 }
  18.             }
  19.          }
  20.          return true;
  21.     }
  22. };

三、解数独

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     bool checkrow[9][10];
  4.     bool checkcol[9][10];
  5.     bool checkgrid[3][3][10];
  6.     void solveSudoku(vector<vector<char>>& board) 
  7.     {
  8.         //初始化
  9.        for(int row=0;row<9;++row)
  10.          for(int col=0;col<9;++col)
  11.          {
  12.             if(board[row][col]!='.')
  13.             {
  14.                 int num=board[row][col]-'0';
  15.                 checkrow[row][num]=checkcol[col][num]=checkgrid[row/3][col/3][num]=true;
  16.             }
  17.          }
  18.         dfs(board);
  19.     }
  20.         bool dfs(vector<vector<char>> &board)//bool用来告诉上一层决策是正确的
  21.          {
  22.            for(int row=0;row<9;++row)
  23.             for(int col=0;col<9;++col)
  24.          {
  25.             if(board[row][col]=='.')
  26.             {
  27.               //开始尝试填数
  28.               for(int num=1;num<=9;++num)
  29.               {
  30.                 if(!checkrow[row][num]&&!checkcol[col][num]&&!checkgrid[row/3][col/3][num])
  31.                 {
  32.                     //说明能填，就填上
  33.                     board[row][col]=num+'0';
  34.                     checkrow[row][num]=checkcol[col][num]=checkgrid[row/3][col/3][num]=true;
  35.                     if(dfs(board)) return true;//去下一个位置填，如果填成功了，返回true
  36.                     //恢复现场
  37.                     board[row][col]='.';
  38.                     checkrow[row][num]=checkcol[col][num]=checkgrid[row/3][col/3][num]=false;
  39.                 }
  40.               }
  41.               return false;//1-9没有一个数能填，说明决策错误
  42.             }
  43.          }
  44.             return true;//安全地填完了，返回true
  45.          }
  46. };

四、单词搜索

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     bool check[6][6];//用来标记选过的位置
  4.     int m,n;
  5.     vector<vector<char>> board;
  6.     string word;
  7.     bool exist(vector<vector<char>>& _board, string _word) 
  8.     {
  9.         board=_board;
  10.         word=_word;
  11.         m=board.size();
  12.         n=board[0].size();
  13.         for(int i=0;i<m;++i)
  14.          for(int j=0;j<n;++j)
  15.           {
  16.              if(board[i][j]==word[0])
  17.              {
  18.                 check[i][j]=true;
  19.                 if(dfs(i,j,1))  return true;
  20.                 check[i][j]=false;
  21.              }
  22.           }
  23.           return false;
  24.     }
  25.     //用向量的方式来定义
  26.      int dx[4]={0,0,-1,1};
  27.      int dy[4]={1,-1,0,0}; //就可以将4个方向改变成一个for循环
  28.     bool dfs(int i,int j,int pos)
  29.     {
  30.         if(pos==word.size())  return true;
  31.         for(int k=0;k<4;++k)
  32.         {
  33.            int x=i+dx[k],y=j+dy[k];
  34.            if(x>=0&&x<m&&y>=0&&y<n&&check[x][y]==false&&board[x][y]==word[pos])
  35.            {
  36.                check[x][y]=true;
  37.                if(dfs(x,y,pos+1)) return true;
  38.                check[x][y]=false;
  39.            }
  40.         }
  41.         return false;//如果四个方向都找不到，说明确实没有可填的数，直接返回
  42.     }
  43. };

五、黄金旷工

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     int ret=0;
  4.     bool check[15][15];
  5.     int m,n;
  6.     int getMaximumGold(vector<vector<int>>& grid) 
  7.     {
  8.       m=grid.size();
  9.       n=grid[0].size();
  10.       for(int i=0;i<m;++i)
  11.         for(int j=0;j<n;++j)
  12.           {
  13.             if(grid[i][j])
  14.             {
  15.                 check[i][j]=true;
  16.                 dfs(grid,i,j,grid[i][j]);
  17.                 check[i][j]=false;
  18.             }
  19.           }
  20.           return ret;
  21.      }
  22.       //用向量的方式来定义
  23.      int dx[4]={0,0,-1,1};
  24.      int dy[4]={1,-1,0,0}; //就可以将4个方向改变成一个for循环
  25.      void dfs(vector<vector<int>>& grid,int i,int j,int count)
  26.      {
  27.         for(int k=0;k<4;++k)
  28.         {
  29.             int x=i+dx[k],y=j+dy[k];
  30.             if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&grid[x][y])
  31.             {
  32.                 check[x][y]=true;
  33.                 dfs(grid,x,y,count+grid[x][y]);
  34.                 check[x][y]=false;
  35.             }
  36.         }
  37.         ret=max(count,ret);
  38.         //for循环结束，确实没得填了，更新
  39.      }
  40. };

六、不同路径III

. - 力扣（LeetCode）

  1. class Solution {
  2. public:
  3.     int ret;
  4.     bool check[20][20];//用来标记
  5.     int m,n,step;//step用来统计可以走的方格个数
  6.     int uniquePathsIII(vector<vector<int>>& grid) 
  7.     {
  8.         ret=0;
  9.         m=grid.size();
  10.         n=grid[0].size();
  11.         step=0;
  12.         int bx=0,by=0;//记录起点
  13.         //先找起点
  14.         for(int i=0;i<m;++i)
  15.           for(int j=0;j<n;++j)
  16.             {
  17.                 if(grid[i][j]==0) ++step;
  18.                 else if(grid[i][j]==1) 
  19.                 {
  20.                     bx=i;
  21.                     by=j;
  22.                 }
  23.             }
  24.         step+=2;//把起点和终点算上，最后走到终点的时候就可以返回了
  25.         check[bx][by]=true;
  26.         dfs(grid,bx,by,1);
  27.         return ret;
  28.     }
  29.     int dx[4]={0,0,-1,1};
  30.     int dy[4]={1,-1,0,0}; //就可以将4个方向改变成一个for循环
  31.     void dfs(vector<vector<int>>& grid,int i,int j,int count)
  32.     {
  33.         if(grid[i][j]==2&&count==step) {++ret;return;}
  34.         for(int k=0;k<4;++k)
  35.         {
  36.             int x=i+dx[k],y=j+dy[k];
  37.             if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&grid[x][y]!=-1)
  38.             {
  39.                 check[i][j]=true;
  40.                 dfs(grid,x,y,count+1);
  41.                 check[i][j]=false;
  42.             }
  43.         }
  44.     }
  45. };

七、小总结

1、矩阵搜索问题经常要用到向量，也就是我们可以通过dx和dy来帮助我们定义方向

2、矩阵搜索要确保走过的位置不再走过，所以此时有两个策略：

（1）标记数组，比较常用

（2）修改原矩阵的内容，但是这样做的话要我们要确保最后能够把它复原 

3、dfs的返回值不一定是void，如果该题目并不只是完全地去统计，而是涉及到我们做出的选择可能会错误的时候，这个时候我们就需要通过bool类型的返回值来帮助我们判断当前的填法是否正确。比如解数独和单词搜索问题

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/394236
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号