织梦cms网站分页打不开,北京做网站开发公司哪家好,网站建设资金投入分析,聊天网站怎么建设算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习四 01.解数独02.单词搜索03.黄金矿工04.不同路径 III 01.解数独
题目链接#xff1a;https://leetcode.cn/problems/sudoku-solver/
编写一个程序#xff0c;通过填充空格来解决数独问题。
数独的解法需 遵循如下规则https://leetcode.cn/problems/sudoku-solver/
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。
示例 1
输入board [[5,3,.,.,7,.,.,.,.],[6,.,.,1,9,5,.,.,.],[.,9,8,.,.,.,.,6,.],[8,.,.,.,6,.,.,.,3],[4,.,.,8,.,3,.,.,1],[7,.,.,.,2,.,.,.,6],[.,6,.,.,.,.,2,8,.],[.,.,.,4,1,9,.,.,5],[.,.,.,.,8,.,.,7,9]]
输出[[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
解释输入的数独如上图所示唯一有效的解决方案如下所示提示
board.length 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
思路
为了存储每个位置的元素我们需要定义一个二维数组。首先我们记录所有已知的数据然后遍历所有需要处理的位置并遍历数字1~9。对于每个位置我们检查该数字是否可以存放在该位置同时检查行、列和九宫格是否唯一。
我们可以使用一个二维数组来记录每个数字在每一行中是否出现一个二维数组来记录每个数字在每一列中是否出现。对于九宫格我们可以以行和列除以3得到的商作为九宫格的坐标并使用一个三维数组来记录每个数字在每一个九宫格中是否出现。在检查是否存在冲突时只需检查行、列和九宫格里对应的数字是否已被标记。如果数字至少有一个位置行、列、九宫格被标记则存在冲突因此不能在该位置放置当前数字。
特别地在本题中我们需要直接修改给出的数组因此在找到一种可行的方法时应该停止递归以防止正确的方法被覆盖。
代码
class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:void solveSudoku(vectorvectorchar board) {for(int i0;i9;i){for(int j0;j9;j){if(board[i][j]!.){int numboard[i][j]-0;row[i][num]col[j][num]grid[i/3][j/3][num]true;}}}dfs(board);}bool dfs(vectorvectorchar board){for(int i0;i9;i){for(int j0;j9;j){if(board[i][j].){for(int num1;num9;num){if(!row[i][num]!col[j][num]!grid[i/3][j/3][num]){board[i][j]0num;row[i][num]col[j][num]grid[i/3][j/3][num]true;if(dfs(board)) return true;board[i][j].;row[i][num]col[j][num]grid[i/3][j/3][num]false;}}return false;}}}return true;}
};02.单词搜索
题目链接https://leetcode.cn/problems/word-search/
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1
输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED
输出true示例 2
输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE
输出true示例 3
输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB
输出false 提示
m board.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成
思路
其实这里完全就是使用暴力搜索的方式。在解决这个问题时我们假设每个位置的元素作为第一个字母然后向相邻的四个方向进行递归并且不能出现重复使用同一个位置的元素。通过深度优先搜索的方式不断地枚举相邻元素作为下一个字母出现的可能性并在递归结束时回溯直到枚举完所有可能性得到正确的结果。
代码
class Solution {const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};int m,n;bool vis[7][7];
public:bool exist(vectorvectorchar board, string word) {mboard.size(),nboard[0].size();for(int i0;im;i){for(int j0;jn;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;}bool dfs(vectorvectorchar board, int i,int j,string word,int pos){if(posword.size()) return true;for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0yn!vis[x][y]board[x][y]word[pos]){vis[x][y]true;if(dfs(board,x,y,word,pos1)) return true;vis[x][y]false;}}return false;}
};03.黄金矿工
题目链接https://leetcode.cn/problems/path-with-maximum-gold/
你要开发一座金矿地质勘测学家已经探明了这座金矿中的资源分布并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量如果该单元格是空的那么就是 0。
为了使收益最大化矿工需要按以下规则来开采黄金
每当矿工进入一个单元就会收集该单元格中的所有黄金。矿工每次可以从当前位置向上下左右四个方向走。每个单元格只能被开采进入一次。不得开采进入黄金数目为 0 的单元格。矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
示例 1
输入grid [[0,6,0],[5,8,7],[0,9,0]]
输出24
解释
[[0,6,0],[5,8,7],[0,9,0]]
一种收集最多黄金的路线是9 - 8 - 7。示例 2
输入grid [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出28
解释
[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
一种收集最多黄金的路线是1 - 2 - 3 - 4 - 5 - 6 - 7。提示
1 grid.length, grid[i].length 150 grid[i][j] 100最多 25 个单元格中有黄金。
思路
和上一题的思路基本一致只不过需添加在对每一次深度遍历时我们记录最大的累加和即可。
代码
class Solution {bool vis[16][16];const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};int m,n,ret0;
public:int getMaximumGold(vectorvectorint grid) {mgrid.size(),ngrid[0].size();for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]){vis[i][j]true;dfs(grid,i,j,grid[i][j]);vis[i][j]false;}}}return ret;}void dfs(vectorvectorint grid,int i,int j,int path){retmax(ret,path);for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0yn!vis[x][y]grid[x][y]){vis[x][y]true;dfs(grid,x,y,pathgrid[x][y]);vis[x][y]false;}}}
};04.不同路径 III
题目链接https://leetcode.cn/problems/unique-paths-iii/
在二维网格 grid 上有 4 种类型的方格
1 表示起始方格。且只有一个起始方格。2 表示结束方格且只有一个结束方格。0 表示我们可以走过的空方格。-1 表示我们无法跨越的障碍。
返回在四个方向上、下、左、右上行走时从起始方格到结束方格的不同路径的数目**。**
每一个无障碍方格都要通过一次但是一条路径中不能重复通过同一个方格。
示例 1
输入[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出2
解释我们有以下两条路径
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)示例 2
输入[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出4
解释我们有以下四条路径
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)示例 3
输入[[0,1],[2,0]]
输出0
解释
没有一条路能完全穿过每一个空的方格一次。
请注意起始和结束方格可以位于网格中的任意位置。提示
1 grid.length * grid[0].length 20
思路
这里和上面的回溯不太一样的地方在于我们必须通过所有的0标记位置首先我们要计算出所有0的个数再加上1个2的位置就是我们要走的路的长度依照要走的长度和起始位置找到不同的路线这里可以使用深度优先遍历找到不同的路径。
代码
class Solution {bool vis[21][21];const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};int m,n,ret0;
public:int uniquePathsIII(vectorvectorint grid) {mgrid.size(),ngrid[0].size();int count0,left,right;for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]0) count;else if(grid[i][j]1){lefti;rightj;}}}vis[left][right]true;dfs(grid,left,right,count1);return ret;}void dfs(vectorvectorint grid,int left,int right,int count){if(grid[left][right]2){if(!count) ret;return;} for(int k0;k4;k){int xleftdx[k],yrightdy[k];if(x0xmy0yn!vis[x][y]grid[x][y]!-1){vis[x][y]true;dfs(grid,x,y,count-1);vis[x][y]false;}}}
};
