[Lc4_dfs] 解数独 | 单词搜索

目录

1.解数独

题解

2.单词搜索

题解

---

1.解数独

链接：37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

---

题解

• 上面的是判断是否是有效数独，这里是填数独。
• 这里还是用上面的三个bool类型数组，来判断这个数能不能放。
• 这里我们一格一格的放，每个格子可以放1-9中其中一个数，但是肯定会是存在 剪枝 情况的。

具体能不能放还是借助那三个bool类型数组来判断。

• 我们递归就是拿着这个棋盘，开始依次遍历，看那个是空的就开始填，填的时候判断一下能填在填不能填就不填。
• 然后能填递归到下一层，但是有可能这个能填的分支下面递归有的位置1 ~ 9都不能填的情况。
• 因此这个分支可能是得不到正确结果的，那上面怎么知道你这种情况不行的呢？
• 因此这个 递归函数 要有一个bool类型的返回值，当遇到某个格子1 ~ 9都不能填直接向上返回一个false，告诉它这个位置你填1不行，你要把这个位置填上2然后在往下试。

递归函数 参数只要把这个board给我就行了。bool dfs(board)。

class Solution {
public:bool checkrow[9][10]={}, checkcol[9][10]={}, grip[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 num = board[i][j]-'0';checkrow[i][num] = checkcol[j][num] = grip[i/3][j/3][num] = true;}}}dfs(board,0,0);}bool dfs(vector<vector<char>>& board, int row, int col) {if(row == 9) return true;  // 修正终止条件if(col == 9) return dfs(board, row+1, 0);if(board[row][col] != '.') {  // 修正非空推进return dfs(board, row, col+1);}for(int i=1; i<=9; i++) {  // 修正数字范围if(!checkrow[row][i] && !checkcol[col][i] && !grip[row/3][col/3][i]) {// 标记数字board[row][col] = i+'0';checkrow[row][i] = checkcol[col][i] = grip[row/3][col/3][i] = true;if(dfs(board, row, col+1)) return true; //！！！！！成功路径要正确终止，来满足递归的返回// 回溯恢复board[row][col] = '.';checkrow[row][i] = checkcol[col][i] = grip[row/3][col/3][i] = false;}}return false;}
};

//！！！！！成功路径要正确终止，来满足递归的返回

if(dfs(board, row, col+1))  return true; 

优化版本：

class Solution {
public:bool checkrow[9][10] = {false};  // 记录行数字存在情况bool checkcol[9][10] = {false};  // 记录列数字存在情况bool grip[3][3][10] = {false};   // 记录九宫格数字存在情况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';mark(i, j, num, true);}}}dfs(board, 0, 0);}bool dfs(vector<vector<char>>& board, int row, int col) {if(row == 9) return true;    // 正确终止条件if(col == 9) return dfs(board, row+1, 0);// 跳过已填数字if(board[row][col] != '.') {return dfs(board, row, col+1);}for(int num = 1; num <= 9; num++) {  // 修正数字范围if(isValid(row, col, num)) {board[row][col] = num + '0';mark(row, col, num, true);if(dfs(board, row, col+1)) return true;// 回溯恢复mark(row, col, num, false);board[row][col] = '.';}}return false;}private:bool isValid(int row, int col, int num) {return !checkrow[row][num] && !checkcol[col][num] &&!grip[row/3][col/3][num];}void mark(int row, int col, int num, bool flag) {checkrow[row][num] = flag;checkcol[col][num] = flag;grip[row/3][col/3][num] = flag;}
};

---

2.单词搜索

链接：79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

---

题解

给一个mxn board二维数组，让在数组中找是否存在字符串单词 word

注意只能上下左右去找，不能斜着找。

我们在这个矩阵中依次找到word里面的所有字符。

• 首先在这个矩阵里面 先一行一行的扫描 找到word里面第一个字符
• 当找到第一个字符时，就从这个字符开始去匹配其他剩余的字符，注意只能上下左右去匹配
• 如果上下左右都不匹配说明这个位置是一次失败的匹配。
• 那就在去找其他位置能匹配的第一个字符。
• 如果找到还是 上下左右去匹配，如果能匹配成功说明这个矩阵有这个单词。

如果把这道题抽象一下，你会发现刚刚的过程就是 解决迷宫常用的方式，深度优先遍历。

如果走不通就回溯一下，再往下走，直到找到一个正确结果为止。

接下来我们考虑 递归函数 如何设计

• 从某个节点开始上下左右匹配下一个字符，所以则函数体干的就是给一个位置然后 上下左右去匹配下一个字符。
• 这个参数首先把这个board给我，然后第一个字符的位置，然后给我要匹配字符串中下一个字符的位置。
• dfs(board，i，j，s，pos)，注意看这个决策树我们从一个位置走可能走失败，上面调用dfs的得知道是找成功还是失败，所以dfs有一个bool类型的返回值
• bool dfs(board，i，j，s，pos) 失败就去另一条路径。

剪枝就是那一个位置能匹配就去走那一个位置。

回溯 一条路径找失败往上走就是回溯，往下走之前你弄了什么，反着来就可以了。

---

下面是细节问题：二维矩阵搜索中，经常要注意的细节。

不能走重复的路

就比如下面的这个位置，一直会是重复的。之前用过的下一次不能在找了。

这里我们有两种方法规避。

1. 用一个bool类型的跟原始数组大小一样的二维数组 bool visit[][]。

• 用这个数组来标记当前这个位置是否被使用过。
• 使用过就把这个位置标记成true。
• 然后到下一层的时候就考虑一下上一个位置是否是ture，是就不走，不是就可以走。

2. 修改原始矩阵的值。

• 比如说把被使用的位置的值修改成*，面试时还是要问一下能否修改，能修改再用这种方法。
• 但是还有一个问题你修改完去往下一层，然后再回来的时候你要把被修改的值在还原回来。

---

这里在写代码去上下左右匹配的时候有两种写法：

• 可以分别写上下左右四个函数去匹配。
• 我们可以用向量的方式，定义上下左右四个位置。
• 然后仅需一次for循环就可以把上下左右都考虑进去了。

单独看这个i，上下左右就是在原始的i基础上要么不变，要么+1，要么-1

所以可以搞一个数组 int dx[4]={0,0,1,-1}; 这个表示i接下来可能的偏移量。

同理j也有四个偏移量 int dy[4]={-1,1,0,0}; 然后这两个就可以上下凑一起使用。

class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;vector<vector<bool>> check;bool exist(vector<vector<char>>& board, string word) {m=board.size();n=board[0].size();check.resize(m,vector<bool>(n,false));// 遍历所有起点for(int i = 0; i < m; ++i) {for(int j = 0; j < n; ++j) {if(board[i][j] == word[0]){check[i][j]=true;if(dfs(board,i,j,word,1)) return true;check[i][j]=false;//以这个点开始搜索，搜索完之后发现不行 //回溯}}}return false;}bool dfs(vector<vector<char>>& board,int i,int j, string s,int pos)
{if(pos == s.size()) return true;for(int k=0;k<4;k++)  //来实现上下左右的移动{int x=i+dx[k],y=j+dy[k];
//这里的检查和bfs 是一样的if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && board[x][y] == s[pos]){if(board[x][y]==s[pos]){check[x][y]=true;if(dfs(board,x,y,s,pos+1)) return true;check[x][y]=false;}}}return false;
} 
};