信息时代网站建设的重要性,制作公司网站的,企业网站建设网站模板,酒店预订网站模板深搜、暴搜、回溯、剪枝#xff08;C#xff09;3 一、解数独1、题目描述2、代码3、解析 二、单词搜索1、题目描述2、代码3、解析 三、黄金矿工1、题目描述2、代码3、解析 四、不同路径III1、题目描述2、代码3、解析 一、解数独
1、题目描述
leetcode链接
2、代码
class… 深搜、暴搜、回溯、剪枝C3 一、解数独1、题目描述2、代码3、解析 二、单词搜索1、题目描述2、代码3、解析 三、黄金矿工1、题目描述2、代码3、解析 四、不同路径III1、题目描述2、代码3、解析 一、解数独
1、题目描述
leetcode链接
2、代码
class Solution
{
public:// 全局变量bool row[9][10]; // 行bool col[9][10]; // 列bool grid[3][3][10]; // 小格子void solveSudoku(vectorvectorchar 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(vectorvectorchar board){for(int i 0; i 9; i){for(int j 0; j 9; j){// 填数if(board[i][j] .){for(int num 1; num 9; num) // 从1-9一个个遍历填数{if(!row[i][num] !col[j][num] !grid[i / 3][j / 3][num]){board[i][j] num 0; // 填入进去row[i][num] col[j][num] grid[i / 3][j / 3][num] true; // 标记用过了if(dfs(board) true) return true; // 表示可以填进去// 恢复现场board[i][j] .;row[i][num] col[j][num] grid[i / 3][j / 3][num] false; // 标记没用}}return false; // 1-9都不行}}}return true; // 走完了填完了返回true}
};3、解析 二、单词搜索
1、题目描述
leetcode链接 2、代码
class Solution
{
public:// 全局变量bool visit[7][7];int m, n;bool exist(vectorvectorchar 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(word[0] board[i][j]){visit[i][j] true; // 标记该点已经被访问过了if(dfs(board, i, j, word, 1/*从第一个位置往下走*/)) return true; // 递归到下一层visit[i][j] false; // 第一个点位置错误找下一个第一个对应的点}}}return false; // 没有访问到}// 定义一个上下左右移动的向量int dx[4] {0, 0, -1, 1}; // x x x-1 x1int dy[4] {1, -1, 0, 0}; // y1 y-1 y ybool dfs(vectorvectorchar board, int i, int j, string word, int pos){// 递归出口if(pos word.size()){return true;}for(int k 0; k 4; k){int x dx[k] i; // x坐标int y dy[k] j; // y坐标// 不越界当前visit数组未被访问过当前字符和word相对应字符相同if(x 0 x m y 0 y n visit[x][y] false word[pos] board[x][y]){visit[x][y] true; // 先定义到访问过if(dfs(board, x, y, word, pos 1)) return true; // 递归下一层visit[x][y] false; // 恢复现场}}return false;}
};3、解析 三、黄金矿工
1、题目描述
leetcode链接 2、代码
class Solution
{
public:// 全局变量bool visit[16][16]; // 标记是否访问过int m, n; // m是行n是列int sum; // 总和int path; // 每次走的路径int getMaximumGold(vectorvectorint 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) // 先找到第一个非零元素{visit[i][j] true; // 标记一下访问过了path grid[i][j]; // 路径加上dfs(grid, i, j, path); // 递归visit[i][j] false; // 找下一个非零元素path - grid[i][j];} }}return sum;}int dx[4] {0, 0, 1, -1}; // 上下左右int dy[4] {1, -1, 0, 0}; // 上下左右void dfs(vectorvectorint grid, int i, int j, int path){// 递归出口sum max(sum, path); // 这里直接用算法max找最大值for(int k 0; k 4; k){int x dx[k] i; // 向量xint y dy[k] j; // 向量yif(x 0 x m y 0 y n visit[x][y] false grid[x][y] ! 0){visit[x][y] true;path path grid[x][y]; // 路径加上dfs(grid, x, y, path);visit[x][y] false; // 恢复现场path path - grid[x][y];}}}
};3、解析 四、不同路径III
1、题目描述
leetcode链接 2、代码
class Solution
{
public:// 全局变量int m, n;bool visit[21][21]; // 用来记录位置是否被访问过int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int ret; // 统计总路数int step; // 记录总共有几个0int uniquePathsIII(vectorvectorint grid) {m grid.size(); // 行n grid[0].size(); // 列int x 0; // 记录1的横坐标int y 0; // 记录1的纵坐标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) // 找到开头{x i;y j;}}}step 2; // 包含上首尾visit[x][y] true; // 标记一下当前位置被使用过dfs(grid, x, y, 1); // 从第一层开始往后递归return ret;}void dfs(vectorvectorint grid, int i, int j, int count/*用来记录每一条路线的0的个数*/){// 递归出口if(grid[i][j] 2){if(count step){ret;}return;}for(int k 0; k 4; k){int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n !visit[x][y] grid[x][y] ! -1){visit[x][y] true;dfs(grid, x, y, count 1);visit[x][y] false;}}}
};3、解析
