当前位置：首页 > article >正文

暴搜、深搜、回溯算法题集

article 2024/11/14 3:51:37

文章目录

1. 全排列
2. 全排列II
3. 子集
4. 子集II
5. 找出所有子集的异或总和再求和
6. 电话号码的字母组合
7. 括号生成
8. 组合
9. 目标和
10. 组合总和
11. 组合总和II
12. 组合总和III
13. 字母大小写全排列
14. 优美的排列
15. N 皇后
16. 有效的数独
17. 解数独
18. 单词搜索
19. 黄金矿工
20. 不同路径III

1. 全排列

在这里插入图片描述

step1：画出决策树：越详细越好
在这里插入图片描述 step2：设计代码
全局变量的设计：

vector<vector<int>> ret; // 用于存储结果
vector<int> path; // 用于存储遍历过程中经过的路径
vector<bool> check; // 对已经选择了的数进行标记，根据标记了的数进行剪枝

DFS函数的设计：
仅需关心某一个节点在干什么事情即可。
细节问题：

回溯：回溯就是一层递归结束之后，变量的状态要复原，对于path则要pop掉最后一个元素；对于check数组则要修改并复原。
递归出口：遇到叶子结点，将结果插入

参考答案：

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<bool> check;
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(check[i] == false) {
                path.push_back(nums[i]);
                check[i] = true;
            } else continue; // check[i] == true则要剪枝
            dfs(nums);
            path.pop_back(); // 回溯: 恢复现场
            check[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        check.resize(nums.size());
        dfs(nums);
        return ret;
    }
};

2. 全排列II

在这里插入图片描述
这题和上一题的不同点：除了在dfs时需要对选过的元素进行剪枝外，当回溯的时候应将重复的元素进行剪枝，避免后序dfs时会出现重复的排列。

写法一：只关心“不合法”的分支

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    vector<bool> check; // check数组用于确保选到的数字不是同一个位置的数
    void dfs(const vector<int>& nums) 
    {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (check[i] == true || 
                (i > 0 && check[i-1] == false && nums[i-1] == nums[i])) 
            {
                continue;
            }
            path.push_back(nums[i]);
            check[i] = true;
            dfs(nums);
            path.pop_back();
            check[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        check.resize(nums.size());
        dfs(nums);
        return ret;
    }
};

写法二：只关心“合法”的分支

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    vector<bool> check; // check数组用于确保选到的数字不是同一个位置的数
    void dfs(const vector<int>& nums) 
    {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (check[i] == false && 
                (i == 0 || check[i-1] == true || nums[i-1] != nums[i]))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        check.resize(nums.size());
        dfs(nums);
        return ret;
    }
};

3. 子集

在这里插入图片描述

解法一：
在这里插入图片描述

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(const vector<int>& nums, int startindex)
    {
        if(startindex == nums.size())
        {
            ret.push_back(path);
            return;
        }

        // 不选, 直接进入下一层递归
        dfs(nums, startindex + 1);
        // 选
        path.push_back(nums[startindex]);
        dfs(nums, startindex + 1);
        path.pop_back(); // 恢复之前递归的状态
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
};

解法二：
在这里插入图片描述

dfs每一轮遍历的节点组成的集合都是结果集，显然要比方法一高效。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    void dfs(const vector<int>& nums, int pos)
    {
        ret.push_back(path);
        for(int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
};

4. 子集II

5. 找出所有子集的异或总和再求和

在这里插入图片描述这题是基于集合那一题的，对求得的集合里面的元素进行异或。

写法一：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    void dfs(const vector<int>& nums, int pos) {
        ret.push_back(path);
        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
        return;
    }
    int subsetXORSum(vector<int>& nums) {
        dfs(nums, 0);
        int sum = 0;
        for (auto& ch1 : ret) {
            int prev = 0;
            for (auto& ch2 : ch1) {
                prev ^= ch2;
            }
            sum += prev;
        }
        return sum;
    }
};

实际上我们无需一整个数组保存所有的节点，我们只需要求得子集中最终异或的结果即可，那么我们只需要用一个变量保存这个结果即可。
写法二：

class Solution {
public:
    int path;
    int sum;
    void dfs(const 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]; // 回溯: 恢复现场
        }
        return;
    }
    int subsetXORSum(vector<int>& nums) {
        dfs(nums, 0);
        return sum;
    }
};

6. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

    0 <= digits.length <= 4
    digits[i] 是范围 ['2', '9'] 的一个数字。

画出决策图很重要，接下来就是照着决策图写代码了。
在这里插入图片描述

class Solution {
public:
    string telnum[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    string path;
    void dfs(const string& digits, int pos)
    {
        if(pos == digits.size())
        {
            ret.push_back(path);
            return;
        }
        int char2num = digits[pos] - '0';
        string letter = telnum[char2num];
        for(int i = 0; i < letter.size(); i++)
        {
            path += letter[i];
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return ret;
        dfs(digits, 0);
        return ret;
    }
};

7. 括号生成

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1
输出：[“()”]

提示：

    1 <= n <= 8

如何保证组合是有效的括号？要满足下面的条件。

整个字符串中，左括号的数量 = 右括号的数量
从头开始的任意一个子串，左括号的数量 >= 右括号的数量

剪枝条件：
记左括号的数目为left，右括号的数目为right，左括号或右括号的总数为n。
当left >= n时，左括号的数目(==时为即将)超过了上限，要剪枝；right >= left时，右括号的数目(即将)超过了左括号，要剪枝
在这里插入图片描述

class Solution {
public:
    vector<string> ret;
    string path;
    int left, right, n;
    void dfs()
    {
        if(right == n)
        {
            ret.push_back(path);
            return;
        }
        // 先插入左括号(
        if(left < n)
        {
            left++;
            path.push_back('(');
            dfs();
            left--;
            path.pop_back();
        }
        // 再插入右括号)
        if(left > right)
        {
            right++;
            path.push_back(')');
            dfs();
            right--;
            path.pop_back();
        } 
    }
    vector<string> generateParenthesis(int _n) {
        n = _n;
        dfs();
        return ret;
    }
};

8. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例 1:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

提示:

    1 <= n <= 20
    1 <= k <= n

在这里插入图片描述这道题给的数据是连续的数字，我们不用担心会出现重复的数字而去创建一个check数组去考虑去重的操作。

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(int n, int k, int startindex)
    {
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        for(int i = startindex; i <= n; i++)
        {
            path.push_back(i);
            dfs(n, k, i + 1); // 每次dfs要从下一个位置开始递归, 不能往回走, 避免重复的组合以及避免选到重复元素
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ret;
    }
};

9. 目标和

在这里插入图片描述

写法一：path作为全局变量

class Solution {
public:
    int ret = 0, path = 0;
    int target;
    void dfs(vector<int>& nums, int pos)
    {
        if(pos >= nums.size())
        {
            if(path == target) ret++;
            return;
        }
        // 先处理'+'
        path += nums[pos];
        dfs(nums, pos + 1);
        path -= nums[pos]; // 恢复现场
        // 再处理'-'
        path -= nums[pos];
        dfs(nums, pos + 1);
        path += nums[pos]; // 恢复现场

        return;
    }
    int findTargetSumWays(vector<int>& nums, int _target) {
        target = _target;
        dfs(nums, 0);
        return ret;
    }
};

写法二：path作为形参

class Solution {
public:
    int ret = 0;
    int target;
    void dfs(vector<int>& nums, int path, int pos)
    {
        if(pos >= nums.size())
        {
            if(path == target) ret++;
            return;
        }
        // 先处理'+'
        dfs(nums, path + nums[pos], pos + 1);
        
        // 再处理'-'
        dfs(nums, path - nums[pos], pos + 1);

        return;
    }
    int findTargetSumWays(vector<int>& nums, int _target) {
        target = _target;
        dfs(nums, 0, 0);
        return ret;
    }
};

10. 组合总和

在这里插入图片描述

解法一：每一层选择数组的元素
在这里插入图片描述

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int target;
    void dfs(vector<int>& candidates, int sum, int pos)
    {
        if(sum == target)
        {
            ret.push_back(path);
            return;
        }
        for(int i = pos; i < candidates.size(); i++)
        {
            if(sum < target) // 对于大于target的部分要剪枝
            {
                path.push_back(candidates[i]);
                dfs(candidates, sum + candidates[i], i); // 注意这里的pos应该是i, i前面的元素会造成重复集合, 应剪枝!!!
                path.pop_back(); // 回溯
            }
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {
        target = _target;
        dfs(candidates, 0, 0);
        return ret;
    }
};

解法二：每一层选择一个元素的个数
在这里插入图片描述

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int target;
    void dfs(vector<int>& candidates, int sum, int pos)
    {
        if(sum == target)
        {
            ret.push_back(path);
            return;
        }
        if(sum > target || pos == candidates.size()) return;

        // 枚举个数
        for(int k = 0; sum + k*candidates[pos] <= target; k++)
        {
            if(k) path.push_back(candidates[pos]);
            dfs(candidates, sum + k*candidates[pos], pos + 1);
        }

        // 回溯, 恢复现场
        for(int k = 1; sum + k*candidates[pos] <= target; k++)
        {
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {
        target = _target;
        dfs(candidates, 0, 0);
        return ret;
    }
};

11. 组合总和II

在这里插入图片描述与组合总和I的不同点：1，组合总和I允许一个元素选多次，组合总和II中每一个元素只能选一次；2，组合总和I的整数数组中无重复元素，而组合总和II中整数数组中有重复元素，因此要对重复的元素进行剪枝。

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<bool> check;
    int aim;
    void dfs(vector<int>& candidates, int sum, int pos)
    {
        if(sum == aim)
        {
            ret.push_back(path);
            return;
        }
        if(sum > aim) return;
        for(int i = pos; i < candidates.size(); i++)
        {
        	// 组合总和II的集合中有重复元素, 要对重复元素进行剪枝去重
            if(i > 0 && candidates[i-1] == candidates[i] && check[i-1] == false) continue; 
            path.push_back(candidates[i]);
            check[i] = true;
            // 这里是i + 1, 因为这题和组合总和I不一样, 这里不能重复选取元素
            dfs(candidates, sum + candidates[i], i + 1); 
            path.pop_back();
            check[i] = false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        aim = target;
        check.resize(candidates.size());
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, 0);
        return ret;
    }
};

12. 组合总和III

在这里插入图片描述这题要注意的是，从1到9选k个数，并且总和为n，第一要控制个数，第二要控制总和。

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int aim;
    void dfs(int k, int sum, int pos)
    {
        if(sum == aim && path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        if(sum > aim || path.size() > k) return;
        for(int i = pos; i <= 9; i++)
        {
            path.push_back(i);
            dfs(k, sum + i, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        aim = n;
        dfs(k, 0, 1);
        return ret;
    }
};

13. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以任意顺序返回输出。

示例 1：

输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

示例 2:

输入: s = “3z4”
输出: [“3z4”,“3Z4”]

提示:

    1 <= s.length <= 12
    s 由小写英文字母、大写英文字母和数字组成

在这里插入图片描述

class Solution {
public:
    vector<string> ret;
    string path;
    void dfs(string& s, int pos)
    {
        if(pos == s.size()) 
        {
            ret.push_back(path);
            return;
        }
        if(s[pos] >= '0' && s[pos] <= '9') // 数字
        {
            path += s[pos];
            dfs(s, pos + 1);
            path.pop_back();
        }
        else // 字母
        {
            char alpha = s[pos];
            if(alpha < 'a' || alpha > 'z')
                alpha -= ('A' - 'a'); // 如果是大写就转换成小写
            // 先选小写
            path += alpha;
            dfs(s, pos + 1);
            path.pop_back();
            // 再选大写
            path += alpha + ('A' - 'a');
            dfs(s, pos + 1);
            path.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }
};

14. 优美的排列

在这里插入图片描述

class Solution {
public:
    int ret;
    vector<bool> check;
    void dfs(int index, int n)
    {
        if(index == n + 1)
        {
            ret++;
            return;
        }
        for(int i = 1; i <= n; i++)
        {
            if(check[i] == false && (i % index == 0 || index % i == 0))
            {
                check[i] = true;
                dfs(index + 1, n);
                check[i] = false;
            }
        }
    }
    int countArrangement(int n) {
        check.resize(n + 1);
        dfs(1, n); // 从1开始枚举, 填n个数
        return ret;
    }
};

15. N 皇后

在这里插入图片描述

算法原理：
从棋盘的每一行开始考虑，for循环负责遍历棋盘的行的每一个格子，将皇后放在格子上；深度优先遍历负责遍历下一行
在这里插入图片描述

剪枝策略：
为确保皇后的同一行，同一列和同一斜线方向上的旗子不会相互攻击，那么就要对上述的决策树进行判断，将符合不被攻击的情况筛选出来。
策略一：
最暴力的解法是，每遍历到一个棋盘，就对这个皇后的同一行，同一列和同一斜线方向上进行遍历，如果遇到了别的旗子，那么就会受到攻击，这种情况不需要记录，直接进行下一趟遍历，那么整个dfs(O(2^N))及寻找是否会受到攻击(O(4N))的时间复杂度是：O(4N * 2^N)。
策略二：
用哈希表记录每个旗子的下标，当我遍历到对应的位置时，能通过当前的下标判断是否和之前的旗子有互相攻击的关系。
（一）当两个旗子横坐标相同时会相互攻击，行方向的哈希表用布尔数组表示，横坐标对应的哈希值为true代表会相互攻击，横坐标对应的哈希值为false代表会相互攻击。布尔数组表示为bool row[n];
（二）当两个旗子纵坐标相同时会相互攻击。布尔数组表示为bool col[n];
（三）斜方向上，我们用截距当作哈希数组的key值，不同旗子的下标算出来的截距如果相同的话，那么就会相互攻击。
情况一：斜率为1
布尔数组表示为bool dig1[2*n];// 表示主对角线
在这里插入图片描述情况二：斜率为-1
布尔数组表示为bool dig2[2*n];// 表示副对角线

class Solution {
public:
    vector<vector<string>> ret;
    vector<string> path;
    vector<bool> checkCol; // 这里无需创建一个checkrow了，因为水平方向我每次添加了元素后还会回溯恢复现场，也就是说我能控制一行只添加一个元素，无需判断
    vector<bool> checkdig1;
    vector<bool> checkdig2;
    void dfs(int n, int row)
    {
        if(row == n)
        {
            ret.push_back(path);
            return;
        }
        for(int col = 0; col < n; col++) // 在这一行放皇后
        {
            // 剪枝
            if(checkCol[col] == true || checkdig1[col - row + n] == true || checkdig2[col + row] == true) continue;
            path[row][col] = 'Q';
            checkCol[col] = checkdig1[col - row + n] = checkdig2[col + row] = true;
            dfs(n, row + 1);
            // 恢复现场
            path[row][col] = '.';
            checkCol[col] = checkdig1[col - row + n] = checkdig2[col + row] = false;
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) {
        path.resize(n);
        for(auto& a : path) a.append(n, '.');

        checkCol.resize(n);
        checkdig1.resize(2*n);
        checkdig2.resize(2*n);
        dfs(n, 0);
        return ret;
    }
};

16. 有效的数独

在这里插入图片描述

如何验证已经填入的数字是否有效？
算法原理：
用hash数组去标记当前行有无重复元素，当前列有无重复元素，9宫格有无重复元素。
（1）当前行有无重复元素
用bool row[9][10]表示，下标含义是：如row[2][3]表示，第2行的元素3是否存在，存在为true，不存在为false。
（2）当前列有无重复元素
用bool col[9][10]表示，下标含义是：如col[8][3]表示，第8列的元素3是否存在，存在为true，不存在为false。
（3）9宫格有无重复元素
在这里插入图片描述

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] == true || col[j][num] == true || grid[i/3][j/3][num] == true)
                        return false;
                    // 遍历过的数字在hash中的位置标记为true
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                }
            }
        }
        return true;
    }
};

17. 解数独

在这里插入图片描述算法原理：

class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];

    bool dfs(vector<vector<char>>& board)
    {
        // 暴力枚举board的每一个格子
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.')
                {
                    // 在空格的位置填入1~9，依次试一遍
                    for(char k = '1'; k <= '9'; k++)
                    {
                        // 判断num是否合法, 不合法就找下一个
                        int num = k - '0';
                        if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num])
                        {
                            // num暂时合法, 先填到board中, 进入下一层递归
                            board[i][j] = k;
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                            if(dfs(board) == true) return true; // 当前层填的没问题, 向上返回true
                            board[i][j] = '.'; // 回溯的时候return false表现在我要恢复原来的状态, 现在的结果不合法
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
                        }
                    }
                    // 能走到这里说明for循环里没有return true
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        // 先把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);
    }
};

18. 单词搜索

在这里插入图片描述

算法原理：
在这里插入图片描述

如何取遍历一个节点的上下左右呢？
向量偏移法：
具体使用见代码实现。
在这里插入图片描述

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0}; // 上下左右的下标x的变化
    int dy[4] = {0, 0, -1, 1}; // 上下左右的下标x的变化
    int m, n;
    bool visit[100][100];
    bool dfs(vector<vector<char>>& board, string word, int x, int y, int pos)
    {
        if(pos == word.size()) return true; // 单词匹配完了还没有出错就返回true

        // 第一个位置找到了, dfs坐标(x,y)的上下左右四个方向, 看有没有符合要求的
        for(int k = 0; k < 4; k++)
        {
            int i = x + dx[k], j = y + dy[k];
            if(    i >= 0 && i < m              // i不能越界
                && j >= 0 && j < n              // j不能越界
                && visit[i][j] == false         // (i,j)未被使用过
                && board[i][j] == word[pos])    // (i,j)位置的值和word[pos]要能匹配
            {
                visit[i][j] = true;
                if(dfs(board, word, i, j, pos + 1)) return true;
                visit[i][j] = false;
            }
        }
        // 四个方向都没找到就回溯, 去找另一个位置
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        // 先找单词的第一个字母
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[0].size(); j++) {
                if(board[i][j] == word[0] && visit[i][j] == false)
                {
                    visit[i][j] = true;
                    if(dfs(board, word, i, j, 1)) return true;
                    visit[i][j] = false;
                }
            }
        }
        return false;
    }
};

19. 黄金矿工

在这里插入图片描述

算法原理：
在这里插入图片描述

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[16][16];
    int ret, m, n;
    void dfs(vector<vector<int>>& grid, int i, int j, int path)
    {
        // 递归出口: 可以不用写, 这题递归出口要写很多判断很麻烦
        // 其实递归出口就隐藏在了下面的for循环中, 当遇到0时就不会进入dfs
        // 每进入一次递归就更新一次结果, 这样能保证不遗漏
        ret = path > ret ? path : ret;
        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
                && grid[x][y] != 0
                && vis[x][y] == false)
            {
                vis[x][y] = true;
                dfs(grid, x, y, path + grid[x][y]);
                vis[x][y] = false;
            }
        }
    }
    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] != 0)
                {
                    vis[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    vis[i][j] = false;
                }
            }
        }
        return ret;
    }
};

20. 不同路径III

在这里插入图片描述

算法原理：
这题别看他是困难题，其实思路和前面两题是一样的，都是运用暴搜的思路，将所有的路径搜索出来，还需要对合法路径进行判断。
合法路径如何判断？
合法路径指的是从1到2，要经过所有的非障碍物的路径。我们可以用一个count记录每次走过的步数，用step表示从1到2的合法路径的步数，比较count和step即可判断是否合法。

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[20][20];
    int m, n;
    int ret = 0, count = 0, step = 2;
    void dfs(vector<vector<int>>& grid, int i, int j) {
        // 走到重点
        if(grid[i][j] == 2)
        {
            if(count == step) ret++; // 判断路径是否合法
            return;
        }
        // 上下左右去dfs
        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
                && grid[x][y] != -1
                && vis[x][y] == false)
            {
                vis[x][y] = true;
                count++;
                dfs(grid, x, y);
                vis[x][y] = false;
                count--;
            }
        }
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        // 1. 统计一共要走多少步, 0的个数 + 2(1和2)
        // 2. 标记1的位置
        int starti = 0, startj = 0;
        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) starti = i, startj = j;

        vis[starti][startj] = true;
        count++;
        dfs(grid, starti, startj);
        return ret;
    }
};