题目链接：电话号码的字母组合

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

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

方法一：回溯

class Solution {
public:
    string list[10] = {
    "",     // 0
    "",     // 1（不用）
    "abc",  // 2
    "def",  // 3
    "ghi",  // 4
    "jkl",  // 5
    "mno",  // 6
    "pqrs", // 7
    "tuv",  // 8
    "wxyz"  // 9
};

    vector<string> ans;
    string t;
    void dfs(string digits,int x) {
        if (x >= digits.size()) {
            ans.push_back(t);
            return ;
        }
        for (int i = 0;i < list[digits[x]-'0'].size();i++) {
            t.push_back(list[digits[x]-'0'][i]);
            dfs(digits,x+1);
            t.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        dfs(digits,0);
        return ans;
    }
};

题目链接：子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

方法一：回溯

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> t;
    void f(vector<int>& nums,int x) {
        if (x >= nums.size()) {
            ans.push_back(t);
            return ;
        }
        t.push_back(nums[x]);
        f(nums,x+1);
        t.pop_back();
        f(nums,x+1);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        f(nums,0);
        return ans;
    }
};

题目链接：全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

方法一：回溯

class Solution {
public:
    vector<vector<int>> ans;
    bool check[12];
    vector<int> t;
    void f(vector<int>& nums,int x) {
        if (x >= nums.size()) {
            ans.push_back(t);
            return ;
        }
        for (int i = 0;i < nums.size();i++) {
            if (!check[i]) {
                check[i] = true;
                t.push_back(nums[i]);
                f(nums,x+1);
                t.pop_back();
                check[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        memset(check, false, sizeof(check));
        f(nums,0);
        return ans;
    }
};

题目链接：腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

方法一：广度优先遍历

class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    int cnt;
    int dis[10][10];
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> q;
        memset(dis,-1,sizeof dis);
        cnt = 0;
        int ans = 0;
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0;j < grid[0].size();j++) {
                if (grid[i][j] == 2) {
                    dis[i][j] = 0;
                    q.push({i,j});
                }else if (grid[i][j] == 1) cnt++;
            }
        }
        while (!q.empty()) {
            pair<int,int> p = q.front();
            q.pop();
            for (int i = 0;i < 4;i++) {
                int tx = p.first+dx[i];
                int ty = p.second+dy[i];
                if (tx < 0 || tx >= grid.size() || ty < 0 || ty >= grid[0].size() || dis[tx][ty] != -1 || !grid[tx][ty]) continue;
                //cnt--;
                dis[tx][ty] = dis[p.first][p.second] + 1;
                q.push({tx,ty});
                if (grid[tx][ty] == 1) {
                    cnt --;
                    ans = dis[tx][ty];
                    if (cnt == 0) {
                        
                        break ;
                    }
                }
            }
        }
        return cnt ? -1 : ans;
    }
};

题目链接：岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

方法一：深度优先遍历

class Solution {
public:
    bool m[301][301];
    void dfs(vector<vector<char>>& grid,int x,int y) {
        m[x][y] = true;
        //grid[x][y] == '0';
        if (x - 1 >= 0 && grid[x-1][y] == '1' && !m[x-1][y]) dfs(grid,x-1,y);
        if (x + 1 < grid.size() && grid[x+1][y] == '1' && !m[x+1][y]) dfs(grid,x+1,y);
        if (y-1 >= 0 && grid[x][y-1] == '1' && !m[x][y-1]) dfs(grid,x,y-1);
        if (y+1 < grid[0].size() && grid[x][y+1] == '1' && !m[x][y+1]) dfs(grid,x,y+1);
    }
    int numIslands(vector<vector<char>>& grid) {
        
        for (int i = 0;i < 300;i++) {
            for (int j = 0;j < 300;j++) {
                m[i][j] = false;
            }
        }
        int ans = 0;
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0;j < grid[0].size();j++) {
                if (grid[i][j] == '1' && m[i][j] == false) {
                    ans++;
                    dfs(grid,i,j);
                }
            }
        }
        return ans;
    }
};