算法学习（十六）—

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，之后的结果仍然是1，2的两次异或相互抵消，所以回溯的时候再异或一下即可
最后就是递归出口，就是每次进入递归的时候，都要 sum += path

class Solution {
public:int path;int sum;int subsetXORSum(vector<int>& nums) {dfs(nums, 0);return sum;    }void dfs(vector<int>& 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:vector<vector<int>> vv;vector<int> path;bool check[9];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return vv;}void dfs(vector<int>& 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:vector<string> ret;string path;string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> 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;vector<string> ret;string path;vector<string> 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:vector<vector<int>> ret;vector<int> path;int N, K;vector<vector<int>> 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(vector<int>& nums, int target) {a = target;dfs(nums, 0);return ret;}void dfs(vector<int>& 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(vector<int>& nums, int target) {a = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& 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;vector<vector<int>> ret;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {a = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& 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个2，1个2，2个2，3个2，4个2，5个2，得到的结果就是0，2，4，6，8，10，由于10已经大于target，所以枚举的2的个数到5时停止枚举，把结果为8的情况统计一下
然后我们固定0个2的结果0，再次枚举3，也是枚举0个3，1个3，2个3，3个3，结果为0，3，6，9，9大于8了，停止枚举，由于没有结果为8，不统计
然后我再次固定0个3的结果，往后再次枚举4的个数，就这样再次一直枚举，和上面相同的步骤
然后再次返回到0个2的结果哪里，然后再次固定 1个2 的结果2再次以相同的步骤再次枚举3和4，这就是解法二
解法二的回溯需要等一个数全部枚举完后再回溯，这样可以减少很多不必要的加减运算

解法二代码：

class Solution {
public:int a;vector<vector<int>> ret;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {a = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& 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;vector<string> ret;vector<string> 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;vector<vector<string>> ret;vector<string> path;bool checkCol[20], checkDig1[20], checkDig2[20];vector<vector<string>> 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(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';//判断这个数字是否是有效的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(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';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& 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(vector<vector<char>>& 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(vector<vector<char>>& 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(vector<vector<int>>& 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(vector<vector<int>>& 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(vector<vector<int>>& 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(vector<vector<int>>& 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;}}}
};