普通网站 手机网站,微信app下载安装官方版,做网站项目的心得,wordpress 导出数据目录
1863. 找出所有子集的异或总和再求和
47. 全排列 Ⅱ
17. 电话号码的字母组合
22. 括号生成
77. 组合
494. 目标和
39. 组合总和
784. 字母大小写全排列
526. 优美的排列
51. N皇后
36. 有效的数独
37. 解数独
79. 单词搜索
1219. 黄金矿工
980. 不同路径 Ⅲ…目录
1863. 找出所有子集的异或总和再求和
47. 全排列 Ⅱ
17. 电话号码的字母组合
22. 括号生成
77. 组合
494. 目标和
39. 组合总和
784. 字母大小写全排列
526. 优美的排列
51. N皇后
36. 有效的数独
37. 解数独
79. 单词搜索
1219. 黄金矿工
980. 不同路径 Ⅲ 1863. 找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和 - 力扣LeetCode 题目意思和我们之前的求子集很相似只是这里多了几步就是要把每个子集的结果都异或一遍然后把所有值相加下面来分析下这道题
还是老样子步骤为①先画决策树 ②再设计代码全局变量dfs函数体回溯剪枝以及递归出口先画决策树如下图首先是全局变量int sum作用是保存所有子集异或后相加的结果int path记录的是当前这一层两个数异或的结果就是不再存1和2这两个数直接存它们异或的结果然后就是dfs函数头的设计和之前是一样的dfs(nums, pos)pos 表示本次递归要从哪个数开始枚举然后就是回溯这个我们可以利用一下异或运算的“消消乐”就是1异或2然后再异或一个2之后的结果仍然是12的两次异或相互抵消所以回溯的时候再异或一下即可最后就是递归出口就是每次进入递归的时候都要 sum path
class Solution {
public:int path;int sum;int subsetXORSum(vectorint nums) {dfs(nums, 0);return sum; }void dfs(vectorint nums, int pos){sum path;for(int i pos; i nums.size(); i){path ^ nums[i];dfs(nums, i 1);path ^ nums[i]; //恢复现场}}
};
47. 全排列 Ⅱ
47. 全排列 II - 力扣LeetCode 全排列我们在上一篇文章中已经讲过大体思路了算法学习十五—— 回溯算法-CSDN博客
这道题只是多了“有重复元素”这一点大逻辑是一样的所以这里我们重点搞一下剪枝其它的就不再赘述下面来分析下这道题
这道题题目给我们的数组中是有重复元素的所以全排列后的结果可能会有重复所以题目就是要求我们干掉重复的全排列返回不重复的结果说到“干掉”最先想到的就是“剪枝”操作所以这道题的重点就是在“剪枝”上先画决策树如下图 所以在这道题中我们的剪枝只会发生在两种情况 同一个节点的所有分支中相同的元素只能选择一次同一个数只能用一次用check数组来搞 然后就是如何用代码实现剪枝其实和前面一样就是加几个if判断即可对于剪枝实现我们有下面两种思考方式
只关心“不合法”的分支就是在递归之前坐下判断如果这个分支不合法就直接返回不再递归。当 check[i] true || nums[i] nums[i - 1] check[i - 1] false 时就是该数已经使用过或者和前面一个数重复了所以不合法至于后面的与操作以上面决策树的 1 1 __ __ 为例这个结果里的两个 1 其实是在不同层次的第一个1是上一层的第二个1是本层的所以两个层次的不做比较还有一个问题当i 0时再 i - 1就越界了所以还要加一个条件最后的判断条件就是check[i] true || (i ! 0 nums[i] nums[i - 1] check[i - 1] false) 只关心“合法”的分支就是当选择条件成立时再进入递归。check[i] false首先是必须要这个位置的值未被使用才有机会进入递归i 0 || nums[i] ! nums[i - 1] || check[i - 1] true就是两个数不一样或者两个数一样但是处于不同层时可以进递归最后的判断条件就是check[i] false (i 0 || nums[i] ! nums[i - 1] || check[i - 1] true 细节处理 如果题目给我们的是[1, 2, 1, 3, 1] 这样的数组那么当我们递归到第二个1时还要去前面看第一个1有没有用过就很麻烦所以我们可以在最开始把数组排序一下 class Solution {
public:vectorvectorint vv;vectorint path;bool check[9];vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return vv;}void dfs(vectorint nums, int pos){if(pos nums.size()){vv.push_back(path);return;}for(int i 0; i nums.size(); i){//思路一只考虑不合法分支if(check[i] true || (i ! 0 nums[i] nums[i - 1] check[i - 1] false)) continue;path.push_back(nums[i]);check[i] true; //表明该位置已被使用dfs(nums, pos 1);path.pop_back(); //恢复现场check[i] false;//思路二只考虑合法分支// if(check[i] false (i 0 || nums[i] ! nums[i - 1] || check[i - 1] true))// {// path.push_back(nums[i]);// check[i] true; //表明该位置已被使用// dfs(nums, pos 1);// path.pop_back(); //恢复现场// check[i] false;// }}}
};
17. 电话号码的字母组合
17. 电话号码的字母组合 - 力扣LeetCode 这道题很简单看示例1并参照图片很容易解决但是当给我们的数字只有两个的时候我们可以用两层for循环解决但是当给我们的数字是9位数甚至更大时再用循环嵌套就不太实际了下面我们来分析下这道题
这道题还是用递归来搞的先画决策树如下图然后是全局变量的设计首先搞一个字符串数组用来解决数组与字符串的映射关系然后是一个path保存每个路径的值最后就是ret用来保存最终结果然后就是 dfs函数体的设计dfs(digits, pos)就是根据题目给的数字翻译成字符串然后pos代表字符串的具体某个位置最后就是回溯过程就是把path的最后一个字符干掉即可最后就是递归出口就是当递归到叶子节点时保存path的结果即可
class Solution {
public:vectorstring ret;string path;string hash[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};vectorstring letterCombinations(string digits) {if(digits.size() 0) return ret;dfs(digits, 0); //从0开始翻译到最后一个位置return ret;}void dfs(const string s, int pos){if(pos s.size()){ret.push_back(path);return;}//把该字符串所有情况翻译一下加到path后面即可for(auto e : hash[s[pos] - 0]) //把字符转为数字并找到对应的字符串{path.push_back(e);dfs(s, pos 1);path.pop_back();}}
};
22. 括号生成
22. 括号生成 - 力扣LeetCode 题目很简单就是给我们一个数字要我们找到相同数量的有效括号的集合并返回下面来分析下这道题
先来分析下什么是“有效括号的组合”①左括号数量 右括号数量 ②从头开始的任意一个字串左括号的数量 右括号的数量只要上面有一个点点不合法那么就不是“有效括号的组合”我们要列举出括号假设 n 3那么只需要6个空然后往这6个空中暴力枚举符合要求的括号即可先画决策树如下图首先是全局变量left表示左括号的数量right表示右括号数量n表示括号的对数然后就是path表示递归的路径然后就是dfs不需要参数因为参数已经在全局里设置好了然后就是dfs干的事其实也很简单当左括号合法时把左括号加到path里右括号同理这样就可以了回溯时一样的干掉path的最后一个递归出口就是当right n也就是右括号为n的时候说明左括号和右括号全搞好了就是到了叶子节点直接返回即可
class Solution {
public:int left, right;vectorstring ret;string path;vectorstring generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(right n) {ret.push_back(path);return;}if(left n) //先加左括号{path (;left;dfs(n);path.pop_back(); //恢复现场left--;}if(right left) //再加右括号{path );right;dfs(n);path.pop_back();right--;}}
};
77. 组合
77. 组合 - 力扣LeetCode 这种排列类型的题都是很相似的所以我们的解题思路和决策树也都很相似下面来分析下这道题
先画决策树如下图枚举的时候只需要从该数的下一个数开始比如 1 往后枚举是从 2 开始2 往后枚举是从 3 开始所以并不需要全局变量来辅助剪枝只要控制下递归参数即可dfs(pos)表示接下来的操作从哪个位置开始然后需要 path 记录路径然后回溯时把最后的数干掉即可当碰到叶子节点时就可返回结果
class Solution {
public:vectorvectorint ret;vectorint path;int N, K;vectorvectorint combine(int n, int k) {N n, K k;dfs(1);return ret;}void dfs(int pos){if(path.size() K){ret.push_back(path);return;}//从起始位置往后枚举for(int i pos; i N; i){path.push_back(i);dfs(i 1); //从添加的这个数的下一个位置开始path.pop_back();}}
};
494. 目标和
494. 目标和 - 力扣LeetCode 这道题其实我们小学时就见过就是给你一个正数数组给里面每个数都添加加号或减号并能使式子的结果 target要我们返回可以通过这种方法构造运算结果 target 的不同表达式的数目下面来分析下这道题
先画决策树如下图所以这道题其实很简单所以我们来搞两种形式的代码①path 是全局变量时候的代码 ②path 作为参数时的代码代表性题目就是我们之前搞得子集那道题算法学习十五—— 回溯算法-CSDN博客 代码一就是当path为全局变量的时候 class Solution
{int path, ret;int a;
public:int findTargetSumWays(vectorint nums, int target) {a target;dfs(nums, 0);return ret;}void dfs(vectorint nums, int pos){if(pos nums.size()){//当数组的数已经枚举完并且path已经等于目标值说明已经找到一种结果if(path a) ret; return;}//加法path nums[pos];dfs(nums, pos 1);path - nums[pos]; //恢复现场就是和前面反着来//减法path - nums[pos];dfs(nums, pos 1);path nums[pos]; }
}; 代码二就是path作为参数传递思路和“子集‘的解法二类似 class Solution
{int ret, a;
public:int findTargetSumWays(vectorint nums, int target) {a target;dfs(nums, 0, 0);return ret;}void dfs(vectorint nums, int pos, int path) //path表示当前节点已经前面枚举之后相加或相减的结果{if(pos nums.size()){//当数组的数已经枚举完并且path已经等于目标值说明已经找到一种结果if(path a) ret; return;}//加法dfs(nums, pos 1, path nums[pos]);//减法dfs(nums, pos 1, path - nums[pos]);}
}; 可以看到能是能通过但是时间复杂度都很高这是因为这道题的最优解其实不是爆搜而是动态规划我们后面学习动态规划时还会遇到
但是作为学习者这道题我们需要掌握的就是当path作为全局和参数时代码大体是如何写的
39. 组合总和
39. 组合总和 - 力扣LeetCode 组合总和有四道题但是第一道是最经典的。题目给我们一个不重复的整数数组同一个数字可以无限选取然后题目要求我们从数组中选一些数加起来 target要我们找出能选多少不同的组合下面来分析下这道题 解法一 先画决策树如下图
解法一代码
class Solution {
public:int a;vectorvectorint ret;vectorint path;vectorvectorint combinationSum(vectorint candidates, int target) {a target;dfs(candidates, 0, 0);return ret;}void dfs(vectorint nums, int pos, int sum){if(sum a){ret.push_back(path);return;}if(sum a || pos nums.size()) return;for(int i pos; i nums.size(); i){path.push_back(nums[i]);dfs(nums, i ,sum nums[i]); //由于可以选重复的数所以第二个参数是i不是i 1path.pop_back();}}
}; 解法二 解法一是根据某一个位置来展开枚举的解法二咱们就根据数来展开
假设还是 [2, 3, 5] target 8这个例子我们先看2我们可以一次枚举0个21个22个23个24个25个2得到的结果就是0246810由于10已经大于target所以枚举的2的个数到5时停止枚举把结果为8的情况统计一下然后我们固定0个2的结果0再次枚举3也是枚举0个31个32个33个3结果为03699大于8了停止枚举由于没有结果为8不统计然后我再次固定0个3的结果往后再次枚举4的个数就这样再次一直枚举和上面相同的步骤然后再次返回到0个2的结果哪里然后再次 固定 1个2 的结果2再次以相同的步骤再次枚举3和4这就是解法二解法二的回溯需要等一个数全部枚举完后再回溯这样可以减少很多不必要的加减运算
解法二代码
class Solution {
public:int a;vectorvectorint ret;vectorint path;vectorvectorint combinationSum(vectorint candidates, int target) {a target;dfs(candidates, 0, 0);return ret;}void dfs(vectorint nums, int pos, int sum){if(sum a){ret.push_back(path);return;}if(sum a || pos nums.size()) return;//解法二for(int i 0; i * nums[pos] sum a; i) //加上sum可以减少枚举次数{if(i) path.push_back(nums[pos]);dfs(nums, pos 1 , sum i * nums[pos]);}//恢复现场for(int i 1; i * nums[pos] sum a; i){path.pop_back();}}
};
784. 字母大小写全排列
784. 字母大小写全排列 - 力扣LeetCode 题目很简单看示例就能看懂下面来分析下这道题
先画决策树如下图
class Solution {
public:string path;vectorstring ret;vectorstring letterCasePermutation(string s) {dfs(s, 0);return ret;}void dfs(string s, int pos){if(path.size() s.length()){ret.push_back(path);return;}char ch s[pos];//改变if((ch a ch z) || (ch A ch Z)){char tmp ch;if(ch a ch z) tmp - 32;else tmp 32;path.push_back(tmp);dfs(s, pos 1);path.pop_back();}//不改变path.push_back(s[pos]);dfs(s, pos 1);path.pop_back();}
};
526. 优美的排列
526. 优美的排列 - 力扣LeetCode 这道题有两道工序要搞一个就是先找到全排列然后判断这个排列是否满足“优美”条件先画决策树如下图
class Solution
{
public:bool check[16];int ret;int countArrangement(int n) {dfs(1, n);return ret;}void dfs(int pos, int n){if(pos n 1){ret;return;}for(int i 1; i n; i){if(!check[i] (pos % i 0 || i % pos 0)){check[i] true;dfs(pos 1, n);check[i] false; //恢复现场}}}
};
51. N皇后
51. N 皇后 - 力扣LeetCode 国际象棋中皇后的攻击机制如上面所说n皇后问题就是要我们在一个 n * n 大小的棋盘内放皇后棋子返回所有符合 n皇后 机制的棋盘如示例图和示例1下面来分析下这道题
这道题的难点就是 “剪枝 代码能力”这道题重点就是要搞一个策略来判断一个位置能不能放皇后有两种策略策略一就是每一个格子来考虑能不能放皇后判断完成后再去下一个格子搞这样遍历完所有的格子即可虽然这种方法时间复杂度是常数但是代码非常不好写很麻烦不推荐用策略二我们每一次我考虑一行的皇后应该放在哪里如下图
所以现在最主要的问题就是如何“剪枝”
剪枝的目的就是考虑当前这个位置能否放上皇后方法一无脑循环就是假设当前位置有皇后然后对各个方向直线上判断有没有其它的皇后这种可以解决但是时间复杂度太高需要4个循环为Log(4n * 2的n次方)但是这道题能过以这个思路我们还可以优化一下以上图为例我们每一行只放一个皇后所以可以少一次循环方法二类似哈希表的策略这个在五子棋这种类似棋盘的问题都可以用我们可以搞三个数组bool row[n] 表示行bool col[n] 表示列如下图然后行列是这样搞的那么搞下斜对角线的数组这个需要一点数学知识如下图然后负对角线也是相同的道理这里不再赘述公式为 y x b就是在数组的 y x 的位置判断是 true 还是 false 即可
class Solution
{
public:int N;vectorvectorstring ret;vectorstring path;bool checkCol[20], checkDig1[20], checkDig2[20];vectorvectorstring solveNQueens(int n) {N n;//先初始化path相当于初始化棋盘path.resize(N);for(int i 0; i n; i){path[i].append(N, .);}dfs(0); //仅需传入一个参数表示要从哪一行开始去枚举return ret;}void dfs(int row){if(row N) //我一行一行去填填到越界了说明已经把 path 里面合法的皇后填完了{ret.push_back(path);return;}for(int col 0; col N; col) //尝试在这一行放皇后{//当列正对角线负对角线都没有皇后时就可以放由于是以行枚举的所以不必判断行if(!checkCol[col] !checkDig1[row - col N] !checkDig2[row col]){path[row][col] Q;checkCol[col] true;checkDig1[row - col N] true;checkDig2[row col] true;dfs(row 1);//恢复现场path[row][col] .;checkCol[col] false;checkDig1[row - col N] false;checkDig2[row col] false;}}}
};
36. 有效的数独
36. 有效的数独 - 力扣LeetCode 这道题其实不是回溯题可以说是哈希表那一类题数独这道题最重要的其实也是剪枝的操作而只要把这道题搞懂了再搞下面的解数独那道题就会很简单下面来分析下这道题
数独就是每一行每一列以及每个3x3的小方格都不能出现重复的数题目要求就是给我们一个已经填了部分数的数独要我们判断这是不是一个有效的数独我们先搞定行跟列的要求可以学习“N皇后”的经验搞两个 bool 类型的数组 row[9][10]以这个数组为例row[2][4] 就是表示“第二行是否出现了4这个数组”为true就是出现了否则为false列同理。就是 col[9][10]所以 col[7][9] 就表示第7列是否存在9这个数 然后就是搞定每一个 3x3 的小方格了如果要暴力的话就是用两个for循环暴力去找但是我们也可以搞一个哈希表把每个 3x3 的小方格看成一个整体那么一个数独就是有9个小方格所以数组就是 bool grid[3][3][10]前面两个数就是表示方格的位置而第三个数就是表示这个方格有没有这个数而且这个方格的位置都很好搞要想知道一个 1x1 的小小方格在哪个 3x3 的小方格里只要把这个 1x1 的方格的位置都 “/3” 即可就能快速知道它在哪一个 3x3 方格里上面的方法就是典型的用“空间换时间”的方法
class Solution
{
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool isValidSudoku(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;//判断这个数字是否是有效的if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) return false;elserow[i][num] col[j][num] grid[i / 3][j / 3][num] true;}}}return true;}
};
37. 解数独
37. 解数独 - 力扣LeetCode 数独的规则这里不再赘述而有了上一道题的经验之后这道题虽然标的是困难但是难度每那么大了下面来分析下这道题
依旧是依次遍历这个二维数组遇到一个空格就往里面填数依次填 1-9 的数然后决策树就有9个分支碍于篇幅问题这里就不画决策树了哈然后就是判断填在这里的9个数合不合法判断方式也很简单就是上一题的那3个数组当不合法时直接返回不再往下递归
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){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;}}//当1-9全部填完之后依旧没有返回true说明这种情况不行return false;}}}return true;}
};
79. 单词搜索
79. 单词搜索 - 力扣LeetCode 给我们一个矩阵然后矩阵有一些字母然后再给我们一个单词要我们设计一个算法判断该单词的字母在矩阵中是否连续存在并且和单词的顺序一样如示例下面来分析下这道题
如下图根据上面的图片中的坐标我们就可以开始画决策树了如下图仔细看就可以发现我们只需要对上面树做一次深度优先遍历即可然后就是函数体的设计就是给我一个位置我要去匹配周围节点的值所以函数体头设计就是bool dfs(board, i, j, s, pos)表示我要在[i, j]这个位置上下左右去匹配s的pos这个位置的字符存不存在然后就是返回值失败了就去试另一条路然后就是回溯和剪枝回溯就是这条路匹配失败往回走的那一段然后剪枝同理 细节二维矩阵搜索中经常要注意的细节 不能走重复的路。假设题目给的数组是 A A C D然后s A A A A如果按照上面的逻辑然后到第二个A时是上下左右去找的那么就会找到前面的A这样就会出问题所以我们要规避这样的情况解决方法①就是建立一个和原矩阵同等规模大小的矩阵visit[][]这个矩阵是bool类型的当一个位置用过时把visit的对应位置设置成true表示这个位置已经用过了所以每次往周围遍历时要先判断下这个数组但是很多人认为上面的方法可能会浪费空间所以我们有了另一个解决方法解决方法②直接修改原矩阵的值。就是匹配了一个字母之后先记录这个字母方便回溯然后把这个字母修改成 . 这种方法在笔试中可以用但是在面试中得问下面试官就是原矩阵允不允许修改但是这道题可以用方法②但是如果某些题的搜索过程很复杂的话恢复现场也就会很麻烦这种情况下还是老老实实用方法①吧 class Solution
{
public:bool vis[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(board[i][j] word[0]) //先找第一个字母{vis[i][j] true;if(dfs(board, i, j, word, 1) true) return true; //从[i][j]位置上下左右匹配word[1]位置的字符vis[i][j] false;}}}return false;}int dx[4] {0, 0, 1, -1}; //搞两个数组数组中存的是x轴和y轴的偏移量(方法二)int dy[4] {-1, 1, 0, 0};bool dfs(vectorvectorchar board, int i, int j, string word, int pos){if(pos word.size()) return true; //当要匹配的位置和word大小一样了那么就表示已经找到了一种情况//写法一上下左右去找可以搞4个函数不推荐//写法二用向量的方式定义上下左右四个位置这个方法是我们在搜索问题中经常用的推荐for(int k 0; k 4; k){int x i dx[k], y j dy[k]; //循环会执行四次if((x 0 y 0) (x m y n) (!vis[x][y] board[x][y] word[pos])) //当坐标没有越界vis矩阵中该元素还没使用过并且能找到和word对应字母匹配{vis[x][y] true;if(dfs(board, x, y, word, pos 1) true) return true;vis[x][y] false; //恢复现场}}return false;}
};
1219. 黄金矿工
1219. 黄金矿工 - 力扣LeetCode 这个题目和我们玩的那个黄金矿工还是有区别的。
这道题和上一道单词搜索很像题目给我们一个二维数组然后我们任意值不为0的位置出发可以往上下左右四个方向遍历每一次遍历将该位置的数相加然后要我们找到相加的数的最大值要求是每次遍历的位置必须是连续的不能遍历值为0的位置每个位置只能遍历一次下面来分析下这道题
这道题最基本的遍历路线和上面单词搜索很相似的如下图其余的步骤比如说函数设计细节处理啥的和上面单词搜索是一样的这里不再赘述
class Solution
{bool vis[16][16];int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;int path, ret;
public: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]){vis[i][j] true;path grid[i][j];dfs(grid, i, j);vis[i][j] false;}}}return ret;}void dfs(vectorvectorint g, int i, int j){ret max(ret, path);for(int k 0; k 4; k){int x i dx[k], y j dy[k];if((x 0 y 0) (x m y n) (!vis[x][y] g[x][y] ! 0)){vis[x][y] true;path g[x][y];dfs(g, x, y);path - g[x][y];vis[x][y] false;}}}
};
980. 不同路径 Ⅲ
980. 不同路径 III - 力扣LeetCode 这道题的前面两个题的“不同路径Ⅰ”和 “不同路径Ⅱ”推荐用动态规划来解决但是这道题不建议用dp这道题建议用爆搜
题目给我们一个网格网格里有很多数字不同的数字有不同的效果要我们返回从起始位置到结束位置的所有路径的数量但是有一个要求就是必须要把所有的0的位置都走一次而且每个0只能走一次下面来分析下这道题 class Solution
{bool vis[21][21];int dx[4] {1, -1, 0, 0};int dy[4] {0, 0, 1, -1};int m, n, step;int beginX, beginY;int ret;
public:int uniquePathsIII(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) {step;}else if(grid[i][j] 1){beginX i;beginY j;step 2; //加上开始和结束的步数}}}vis[beginX][beginY] true;dfs(grid, beginX, beginY, 1); //从起始位置开始遍历return ret;}void dfs(vectorvectorint g, int i, int j, int count){if(g[i][j] 2){if(count step) ret;return;}for(int k 0; k 4; k){int x i dx[k], y j dy[k];if((x 0 y 0) (x m y n) (!vis[x][y] g[x][y] ! -1)){vis[x][y] true;dfs(g, x, y, count 1);vis[x][y] false;}}}
};
