LeetCode 搜索回溯专题

秒速五厘米 2022-08-28 14:57 180阅读 0赞

# 子集 组合问题 #

## [78. 子集][78.] ##

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

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

示例 1：

> 输入：nums = \[1,2,3\]  
> 输出：\[\[\],\[1\],\[2\],\[1,2\],\[3\],\[1,3\],\[2,3\],\[1,2,3\]\]

示例 2：

> 输入：nums = \[0\]  
> 输出：\[\[\],\[0\]\]

class Solution {
        
    public:
        vector<int> sub = {
        };
        vector<vector<int>> res;
        vector<vector<int>> subsets(vector<int>& nums) {
        
            sort(nums.begin(), nums.end());
            solve(nums, 0);
            return res;
        }
        void solve(vector<int> &nums, int cur){
        
            res.push_back(sub);
            if(cur == nums.size()) return;
            for(int i=cur; i<nums.size(); i++){
        
                sub.push_back(nums[i]);
                solve(nums, i+1);
                sub.pop_back();
            }
        }
    };

## [90. 子集 II][90. _ II] ##

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

示例 1：

> 输入：nums = \[1,2,2\]  
> 输出：\[\[\],\[1\],\[1,2\],\[1,2,2\],\[2\],\[2,2\]\]

示例 2：

> 输入：nums = \[0\]  
> 输出：\[\[\],\[0\]\]

class Solution {
        
    public:
        vector<int> sub;
        vector<vector<int>> res;
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        
            sort(nums.begin(), nums.end()); // 先排序
            dfs(nums, 0);
            return res;
        }
        void dfs(vector<int>& nums, int cur){
        
            res.push_back(sub);
            if(cur == nums.size()) return;
            for(int i=cur; i<nums.size(); ++i){
        
                if(i > cur && nums[i] == nums[i-1]) continue; // 如果当前有数字和前一个相等则跳过 
                sub.push_back(nums[i]);
                dfs(nums, i+1);
                sub.pop_back();
            }
        }
    };

## [77. 组合][77.] ##

给定两个整数 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\]\]

class Solution {
        
    public:
        vector<vector<int>> combine(int n, int k) {
        
            vector<vector<int>> res;
            vector<int> subRes;
            solve(res, subRes, 0, 1, n, k);
            return res;
        }
    
        void solve(vector<vector<int>> &res, vector<int> &subRes, int curIndex, int curNum, int n, int k)
        {
        
            if(curIndex == k)
            {
        
                res.push_back(subRes);
                return;
            }
            for(int i=curNum; i<=n; i++)
            {
        
                subRes.push_back(i);
                solve(res, subRes, curIndex+1, i+1, n, k);
                subRes.pop_back();
            }
        }
    };

## [39. 组合总和][39.] ##

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

> 输入: candidates = \[2,3,6,7\], target = 7  
> 输出: \[\[7\],\[2,2,3\]\]

class Solution {
        
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
            vector<vector<int>> res;
            vector<int> subRes;
            sort(candidates.begin(), candidates.end());
            solve(res, subRes, candidates, 0, target);
            return res;
        }
    
        void solve(vector<vector<int>> &res, vector<int> &subRes, vector<int> &candidates, int start, int target)
        {
        
            if(target == 0)
            {
        
                res.push_back(subRes);
                return;
            }
            for(int i=start; i<candidates.size(); i++)
            {
        
                if(target - candidates[i] < 0) break;
                subRes.push_back(candidates[i]);
                solve(res, subRes, candidates, i, target-candidates[i]);
                subRes.pop_back();
            }
        }
    };

## [40. 组合总和 II][40. _ II] ##

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

> 输入: candidates = \[10,1,2,7,6,1,5\], target = 8,  
> 输出:  
> \[  
> \[1,1,6\],  
> \[1,2,5\],  
> \[1,7\],  
> \[2,6\]  
> \]

关键代码是：

> if(i>start && candidates\[i\] == candidates\[i-1\]) continue;

class Solution {
        
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
            vector<vector<int>> res;
            vector<int> subRes;
            sort(candidates.begin(), candidates.end());
            solve(res, subRes, candidates, 0, target);
            return res;
        }
    
        void solve(vector<vector<int>> &res, vector<int> &subRes, vector<int>& candidates, int start, int target)
        {
        
            if(target == 0)
            {
        
                res.push_back(subRes);
                return;
            }
            for(int i=start; i<candidates.size(); i++)
            {
        
                if(target - candidates[i] < 0) break;
                if(i>start && candidates[i] == candidates[i-1]) continue;
                subRes.push_back(candidates[i]);
                solve(res, subRes, candidates, i+1, target-candidates[i]);
                subRes.pop_back();
            }
        }
    };

## [22. 括号生成][22.] ##

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

输入：n = 3  
输出：\["((()))","(()())","(())()","()(())","()()()"\]

class Solution {
        
    public:
        vector<string> res;
        vector<string> generateParenthesis(int n) {
        
            string str = "";
            dfs(str, 0, 0, n);
            return res;
        }
    
        void dfs(string &str, int cntL, int cntR, int n){
        
            if(cntL == n && cntR == n){
        
                res.push_back(str);
                return;
            }   
            if(cntL < n){
        
                str += "(";
                dfs(str, cntL+1, cntR, n);
                str.pop_back();
            }
            if(cntL <= n && cntL > cntR){
        
                str += ')';
                dfs(str, cntL, cntR+1, n);
                str.pop_back();
            }
           
        }
    };

--------------------

# 全排列问题 #

## [46. 全排列][46.] ##

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

示例 1：

> 输入：nums = \[1,2,3\]  
> 输出：\[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]

示例 2：

> 输入：nums = \[0,1\]  
> 输出：\[\[0,1\],\[1,0\]\]

示例 3：

> 输入：nums = \[1\]  
> 输出：\[\[1\]\]

*  递归解决

// 递归解决
    class Solution {
        
    public:
        vector<vector<int>> res;
    
        vector<vector<int>> permute(vector<int>& nums) {
        
            //递归解决
            vector<int> cur;
            dfs(cur, nums, 0);
            return res;
        }
    
        void dfs(vector<int>& cur, vector<int>& nums, int index){
        
            if(index == nums.size()){
        
                res.push_back(cur);
                return;
            }
            for(int i=0; i<nums.size(); ++i){
        
                int ok = 1;
                for(int j=0; j<index; ++j){
        
                    if(cur[j] == nums[i]){
        
                        ok = 0;
                        break;
                    }
                }
                if(ok){
        
                    cur.push_back(nums[i]);
                    dfs(cur, nums, index+1);
                    cur.pop_back();
                }
            }
        }
    };

*  next\_permutation(nums.begin(), nums.end())

class Solution {
        
    public:
        vector<vector<int>>res;
        vector<vector<int>> permute(vector<int>& nums) {
        
            sort(nums.begin(), nums.end());
            do{
        
                vector<int> v;
                for(int i=0; i<nums.size(); ++i){
        
                    v.push_back(nums[i]);
                }
                res.push_back(v);
            }while(next_permutation(nums.begin(), nums.end()));
            return res;
        }
    };

## [47. 全排列 II][47. _ II] ##

给定一个**可包含重复数字**的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

> 输入：nums = \[1,1,2\]  
> 输出：  
> \[\[1,1,2\],  
> \[1,2,1\],  
> \[2,1,1\]\]

示例 2：

> 输入：nums = \[1,2,3\]  
> 输出：\[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]

这里和上一题的不同之处在于它可包含重复数字，因此需要做剪枝操作来排除可能重复的全排列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]

class Solution {
        
    public:
        vector<vector<int>> res;
        vector<vector<int>> permuteUnique(vector<int>& nums) {
        
            vector<int> cur;
            vector<int> visited(nums.size(), 0);
            sort(nums.begin(), nums.end());
            dfs(cur, nums, visited, 0);
            return res;
        }
        void dfs(vector<int>& cur, vector<int>& nums, vector<int>& visited, int index){
        
            if(index == nums.size()){
        
                res.push_back(cur);
                return;
            }
            for(int i=0; i<nums.size(); ++i){
        
                if(visited[i] || (i>0 && nums[i] == nums[i-1] && visited[i-1]==0)){
        
                    continue; // 如果当前已经使用 或者 当前数字与前一个数字一样且已被撤销，则剪枝跳过
                }
                visited[i] = true;
                cur.push_back(nums[i]);
                dfs(cur, nums, visited, index+1);
                cur.pop_back();
                visited[i] = false;
            }
        }
    };

## [784. 字母大小写全排列][784.] ##

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

> 输入：S = “a1b2”  
> 输出：\[“a1b2”, “a1B2”, “A1b2”, “A1B2”\]  
> 输入：S = “3z4”  
> 输出：\[“3z4”, “3Z4”\]  
> 输入：S = “12345”  
> 输出：\[“12345”\]

提示：

*  S 的长度不超过12。
 *  S 仅由数字和字母组成。

class Solution {
        
    public:
        vector<string> res;
        vector<string> letterCasePermutation(string s) {
        
            string cur = "";
            dfs(cur, s, 0);
            return res;
        }
        void dfs(string &cur, string s, int index){
        
            if(index == s.length()){
        
                res.push_back(cur);
                return;
            }
            if(isdigit(s[index])){
        
                cur += s[index];
                dfs(cur, s, index+1);
                cur.pop_back();
            }else{
        
                cur += tolower(s[index]);
                dfs(cur, s, index+1);
                cur.pop_back();
                cur += toupper(s[index]);
                dfs(cur, s, index+1);
                cur.pop_back();
            }
        }
    };

## [剑指 Offer 38. 字符串的排列][Offer 38.] ##

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

> 输入：s = “abc”  
> 输出：\[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”\]

--------------------

# 搜索问题 #

## [37. 解数独][37.] ##

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。  
数字 1-9 在每一列只能出现一次。  
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）  
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例：  
![在这里插入图片描述][5f68f408a6e14ad7b19d18151f9f47de.png]  
![在这里插入图片描述][562c05dc29534a5282410d096fad71a5.png]

## [79. 单词搜索][79.] ##

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

> 输入：board = \[\[“A”,“B”,“C”,“E”\],\[“S”,“F”,“C”,“S”\],\[“A”,“D”,“E”,“E”\]\], word = “ABCCED”  
> 输出：true

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_10_color_FFFFFF_t_70_g_se_x_16]

## [面试题 08.12. 八皇后][08.12.] ##

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展

示例:

> 输入：4  
> 输出：\[\[".Q…","…Q",“Q…”,"…Q."\],\["…Q.",“Q…”,"…Q",".Q…"\]\]  
> 解释: 4 皇后问题存在如下两个不同的解法。  
> \[  
> \[".Q…", // 解法 1  
> “…Q”,  
> “Q…”,  
> “…Q.”\],  
> \["…Q.", // 解法 2  
> “Q…”,  
> “…Q”,  
> “.Q…”\]  
> \]

## [131. 分割回文串][131.] ##

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

> 输入：s = “aab”  
> 输出：\[\[“a”,“a”,“b”\],\[“aa”,“b”\]\]

示例 2：

> 输入：s = “a”  
> 输出：\[\[“a”\]\]

这是整理的LeetCode上的搜索专题。

## BFS ##

这是一种解题框架，使用队列数据结构。

最经典的一类题就是迷宫最短路径问题：

### [1091. 二进制矩阵中的最短路径][1091.] ###

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格都的值都是 0 。  
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。  
畅通路径的长度 是该路径途经的单元格总数。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]

> 输入：grid = \[\[0,1\],\[1,0\]\]  
> 输出：2

这种题目就是一种典型BFS解决的题型。

首先需要定义一下节点状态结构体，包含位置信息和其所走的单元格总数。

然后需要定义一下队列作BFS的过程。

注意要用一个标记数组来标记已经遍历过的节点，防止再次被遍历。

class Solution
    {
        
    public:
        struct Node
        {
        
            int x;
            int y;
            int cnt;
        };
        const int dir[8][2] = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}, {
        1, 1}, {
        1, -1}, {
        -1, 1}, {
        -1, -1}};
        int visited[105][105];
        int shortestPathBinaryMatrix(vector<vector<int>> &grid)
        {
        
            int n = grid.size(), m = grid[0].size();
            if (grid[0][0] == 1 || grid[n - 1][m - 1])
                return -1;
            Node u = {
        0, 0, 1};
            queue<Node> que;
            que.push(u);
            visited[0][0] = 1;
            while (!que.empty())
            {
        
                Node v = que.front();
                que.pop();
                if (v.x == n - 1 && v.y == m - 1)
                {
        
                    return v.cnt;
                }
                for (int i = 0; i < 8; ++i)
                {
        
                    int dx = v.x + dir[i][0];
                    int dy = v.y + dir[i][1];
                    if (dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dx][dy] || visited[dx][dy])
                        continue;
                    Node u = {
        dx, dy, v.cnt+1};
                    visited[dx][dy] = 1;
                    que.push(u);
                }
            }
            return -1;
        }   
    }
    ;

### [127. 单词接龙][127.] ###

字典 wordList 中从单词 beginWord 和 endWord 的 **转换序列** 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。  
序列中最后一个单词是 endWord 。  
每次转换只能改变一个字母。  
转换过程中的中间单词必须是字典 wordList 中的单词。  
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

> 输入：beginWord = “hit”, endWord = “cog”, wordList = \[“hot”,“dot”,“dog”,“lot”,“log”,“cog”\]  
> 输出：5  
> 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2：

> 输入：beginWord = “hit”, endWord = “cog”, wordList = \[“hot”,“dot”,“dog”,“lot”,“log”\]  
> 输出：0  
> 解释：endWord “cog” 不在字典中，所以无法进行转换。

看到最短转换序列的长度可以想到BFS

class Solution {
        
    public:
        //确定俩个单词能否互相转换
        bool exchange_word(const string& a, const string& b) {
        
            int time = 0;
            int len = a.size();
            for (int i = 0; i < len; ++i) {
        
                if (a[i] != b[i]) ++time;
                if (time > 1) return false;
            }
            return time == 1;
        }
    
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        
            unordered_set<string> word_set(wordList.begin(), wordList.end());
            if (word_set.count(endWord) == 0) return 0; // 如果endWord不在wordList直接返回0  
    
            queue<string> q;
            q.push(beginWord);
    
            //必须消除已经是树节点的单词
            word_set.erase(beginWord);
            int i = 1;
    
            while (!q.empty()) {
        
                int size = q.size();                //记住当前队列的长度
                for (int j = 0; j < size; ++j) {
            //for循环pop出队列所有元素
                    auto str = q.front(); q.pop();  
                    vector<string> tmp;             //保存str能够转换的单词
                    for (const string& word : word_set) {
        
                        if (exchange_word(str, word)) {
        
                            if (word == endWord) return i + 1;
                            tmp.push_back(word);
                            q.push(word);
                        }
                    }
                    //tmp中的单词已经是树中的节点,我们需要erase它使得后续的树节点不重复
                    for (const auto& str : tmp) word_set.erase(str);
                }
                ++i;
            }
            return 0;
        }
    };

## DFS ##

### [695. 岛屿的最大面积][695.] ###

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

> \[\[0,0,1,0,0,0,0,1,0,0,0,0,0\],  
> \[0,0,0,0,0,0,0,1,1,1,0,0,0\],  
> \[0,1,1,0,1,0,0,0,0,0,0,0,0\],  
> \[0,1,0,0,1,1,0,0,1,0,1,0,0\],  
> \[0,1,0,0,1,1,0,0,1,1,1,0,0\],  
> \[0,0,0,0,0,0,0,0,0,0,1,0,0\],  
> \[0,0,0,0,0,0,0,1,1,1,0,0,0\],  
> \[0,0,0,0,0,0,0,1,1,0,0,0,0\]\]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

class Solution {
        
    public:
        int res = 0;
        const int dir[4][2] = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
        int cur_area = 1;
        int maxAreaOfIsland(vector<vector<int>>& grid) {
        
            int n = grid.size(), m = grid[0].size();
            vector<vector<int>> visited(n, vector<int>(m));
            for(int i=0; i<n; ++i){
        
                for(int j=0; j<m; ++j){
        
                    if(grid[i][j] == 1 && visited[i][j] == 0){
        
                        cur_area = 1;
                        dfs(i, j, grid, visited);
                        res = max(res, cur_area);
                    }
                }
            }
            return res;
        }
    
        void dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& visited){
        
            visited[x][y] = 1;
            int n = grid.size(), m = grid[0].size();
            for(int i=0; i<4; ++i){
        
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                if(dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dx][dy] == 0 || visited[dx][dy]) continue;
                cur_area++;
                dfs(dx, dy, grid, visited);
            }
        }
    };

### [200. 岛屿数量][200.] ###

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

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

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

示例 1：

> 输入：grid = \[  
> \[“1”,“1”,“1”,“1”,“0”\],  
> \[“1”,“1”,“0”,“1”,“0”\],  
> \[“1”,“1”,“0”,“0”,“0”\],  
> \[“0”,“0”,“0”,“0”,“0”\]  
> \]  
> 输出：1

示例 2：

> 输入：grid = \[  
> \[“1”,“1”,“0”,“0”,“0”\],  
> \[“1”,“1”,“0”,“0”,“0”\],  
> \[“0”,“0”,“1”,“0”,“0”\],  
> \[“0”,“0”,“0”,“1”,“1”\]  
> \]  
> 输出：3

class Solution {
        
    public:
        int res = 0;
        const int dir[4][2] = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
        int numIslands(vector<vector<char>>& grid) {
        
            int n = grid.size(), m = grid[0].size();
            vector<vector<int>> visited(n, vector<int>(m, 0));
            for(int i=0; i<n; ++i){
        
                for(int j=0; j<m; ++j){
        
                    if(grid[i][j] == '1' && visited[i][j] == 0){
        
                        dfs(i, j, grid, visited, n, m);
                        res++;
                    }
                }
            }
            return res;
        }
    
        void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<int>>& visited, int n, int m){
        
            visited[x][y] = 1;
            for(int i = 0; i<4; ++i){
        
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                if(dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dx][dy] == '0' || visited[dx][dy]) continue;
                dfs(dx, dy, grid, visited, n, m);
            }
        }
    };

### [547. 省份数量][547.] ###

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected\[i\]\[j\] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected\[i\]\[j\] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

> 输入：isConnected = \[\[1,1,0\],\[1,1,0\],\[0,0,1\]\]  
> 输出：2

示例 2：

> 输入：isConnected = \[\[1,0,0\],\[0,1,0\],\[0,0,1\]\]  
> 输出：3

这是一道**并查集**的题目，也是有框架模板的。

[78.]: https://leetcode-cn.com/problems/subsets/
[90. _ II]: https://leetcode-cn.com/problems/subsets-ii/
[77.]: https://leetcode-cn.com/problems/combinations/
[39.]: https://leetcode-cn.com/problems/combination-sum/
[40. _ II]: https://leetcode-cn.com/problems/combination-sum-ii/
[22.]: https://leetcode-cn.com/problems/generate-parentheses/
[46.]: https://leetcode-cn.com/problems/permutations/
[47. _ II]: https://leetcode-cn.com/problems/permutations-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20220828/1765beaef9584927b2bcdf292bee69bb.png
[784.]: https://leetcode-cn.com/problems/letter-case-permutation/
[Offer 38.]: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
[37.]: https://leetcode-cn.com/problems/sudoku-solver/
[5f68f408a6e14ad7b19d18151f9f47de.png]: /images/20220828/7327ba32995540cba45141fab4531610.png
[562c05dc29534a5282410d096fad71a5.png]: /images/20220828/1ab93bd31dd642eaab45df28a34934dc.png
[79.]: https://leetcode-cn.com/problems/word-search/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a4b5f51bd09949659771e7b541743a1f.png
[08.12.]: https://leetcode-cn.com/problems/eight-queens-lcci/
[131.]: https://leetcode-cn.com/problems/palindrome-partitioning/
[1091.]: https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70 1]: /images/20220828/46c6023594b04620b1daa4e3bd94b9cb.png
[127.]: https://leetcode-cn.com/problems/word-ladder/
[695.]: https://leetcode-cn.com/problems/max-area-of-island/
[200.]: https://leetcode-cn.com/problems/number-of-islands/description/
[547.]: https://leetcode-cn.com/problems/number-of-provinces/