Skip to main content

11-图与搜索

图​

面试题 04.01. 节点间通路​

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        //BFS
        unordered_map<int,unordered_set<int>> umap;
        for(auto x : graph) umap[x[0]].insert(x[1]);
        vector<bool> visited(n,false);
        queue<int> que;
        que.push(start);
        while(!que.empty())
        {
            int front = que.front();
            que.pop();
            if(front == target) return true;
            if(visited[front]) continue;
            visited[front] = true;
            for(int x : umap[front])
            {
                if(!visited[x]) que.push(x);
            }
        }
        return false;
    }
};

133. 克隆图**​


class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_set<Node*> uset;
        function<void(Node*)> dfs = [&](Node* root){
            if(!root || uset.find(root) != uset.end()) return;
            uset.insert(root);
            for(int i = 0; i < root->neighbors.size();i++) 
                dfs(root->neighbors[i]);
        };
        dfs(node);
        unordered_map<Node*,Node*> umap;
        for(Node* x : uset)
        {
            Node* new_node = new Node(x->val,x->neighbors);
            umap[x] = new_node;
        }

        for(auto x : umap)
        {
            Node* new_node = x.second;
            for(int i = 0; i < new_node->neighbors.size();i++)
            {
                new_node->neighbors[i] = umap[new_node->neighbors[i]];
            }
        }

        return umap[node];
    }
};

拓扑排序​

拓扑排序（topological sort）是一种常见的，对有向无环图排序的算法。给定有向无环图中的 N 个节点，我们把它们排序成一个线性序列；若原图中节点 i 指向节点 j，则排序结果中 i 一定在 j 之前。拓扑排序的结果不是唯一的，只要满足以上条件即可。

我们可以先建立一个邻接矩阵表示图，方便进行直接查找。这里注意我们将所有的边反向， 使得如果课程 i 指向课程 j，那么课程 i 需要在课程 j 前面先修完。这样更符合我们的直观理解。 拓扑排序也可以被看成是广度优先搜索的一种情况：我们先遍历一遍所有节点，把入度为 0 的节点（即没有前置课程要求）放在队列中。在每次从队列中获得节点时，我们将该节点放在目 前排序的末尾，并且把它指向的课程的入度各减 1；如果在这个过程中有课程的所有前置必修课 都已修完（即入度为 0），我们把这个节点加入队列中。当队列的节点都被处理完时，说明所有的 节点都已排好序，或因图中存在循环而无法上完所有课程。

210. 课程表 II​

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> matrix(numCourses,vector<int>(numCourses,0)); // 邻接矩阵
        vector<int> degree(numCourses,0); //入度
        queue<int> que;
        vector<int> res;
        for(int i = 0; i < prerequisites.size();i++)
        {
            matrix[prerequisites[i][1]][prerequisites[i][0]] = 1;
            degree[prerequisites[i][0]]++;
        }
        for(int i = 0; i < degree.size();i++)
        {
            if(degree[i] == 0) que.push(i);
        }
        while(!que.empty())
        {
            int top = que.front();
            que.pop();
            res.push_back(top);
            for(int i = 0; i < numCourses;i++)
            {
                if(matrix[top][i] == 1) 
                {
                    matrix[top][i] = 0;
                    degree[i]--;
                    if(degree[i] == 0)que.push(i);
                }
            }
        }
        if(accumulate(degree.begin(),degree.end(),0) > 0) return {};
        else return res;
    }
};

310. 最小高度树***​

内层所有节点都是res

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        //拓扑排序 ， 洋葱剥壳 -- 度为 1 的开始
        vector<vector<short>> matrix(n);
        vector<int> degree(n,0);
        for(auto x : edges)
        {
            matrix[x[0]].push_back(x[1]);
            matrix[x[1]].push_back(x[0]);
            degree[x[0]]++;
            degree[x[1]]++;
        }
        vector<int> res;
        queue<short> que;
        for(int i = 0; i < n;i++)
            if(degree[i] == 1) que.push(i);
        while(!que.empty())
        {
            int size = que.size();
            res = vector<int>();
            while(size--)
            {
                short front = que.front();
                que.pop();
                res.push_back(front); // 添加节点 当最后一层时 就不会在循环了

                for(int i: matrix[front])
                {
                    degree[i]--;
                    if(degree[i] == 1) que.push(i);
                }  

            }
        }
        
        return res;
    }
};

深度优先搜索​

dfs 与 bfs 区别

1.dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，在换方向（换方向的过程就涉及到了回溯）。 2.bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

代码框架

图的深度优先搜索类似树的前序遍历

图的广度优先搜索类似树的层序遍历

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

深搜三部曲

  1. 确认递归函数，参数

    void dfs(参数)

    Copy

    通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。

    一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局遍历，避免让我们的函数参数过多。

    vector<vector<int>> result; // 保存符合条件的所有路径
    vector<int> path; // 起点到终点的路径
    void dfs (图，目前搜索的节点)

    Copy

2.确认终止条件

if (终止条件) {
    存放结果;
    return;
}

Copy

终止添加不仅是结束本层递归，同时也是我们收获结果的时候。

3.处理目前搜索节点出发的路径

一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。

for (选择：本节点所连接的其他节点) {
    处理节点;
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

79. 单词搜索​

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
        
        function<bool(int ,int ,int)> dfs = [&](int i , int j ,int count){
            if(count == word.size()) return true;
            if(i < 0 || i >= board.size() ||j < 0 || j >= board[0].size() || visited[i][j] || word[count] != board[i][j]) return false;
            visited[i][j] = true;
            bool u = dfs(i - 1, j ,count + 1);
            bool d = dfs(i + 1, j ,count + 1);
            bool l = dfs(i, j - 1,count + 1);
            bool r = dfs(i, j + 1,count + 1);
            visited[i][j] = false;
            return u || d || l || r;
        };

        for(int i = 0 ; i < board.size();i++)
        {
            for(int j = 0 ; j < board[0].size();j++)
            {
                if(dfs(i,j,0)) return true;
            }
        }
        return false;
    }
};

841. 钥匙和房间​

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool>visit(rooms.size(),false);
        function<void (int)> dfs = [&](int i)
        {
            if(i > rooms.size() || visit[i]) return;
            visit[i] = true;
            for( int j = 0 ; j < rooms[i].size(); j++)
            {
                dfs(rooms[i][j]);
            }
        };
        dfs(0);
        return accumulate(visit.begin(),visit.end(),0) == visit.size();
    }
};

200. 岛屿数量​

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> choose(grid.size(),vector<bool>(grid[0].size(),false));
        int res = 2;
        function<void(int ,int,int)> dfs = [&](int i ,int j, int k)
        {
            if(i < 0 || j < 0|| i >= grid.size() || j >= grid[0].size()||choose[i][j]||grid[i][j] == '0') return;
            grid[i][j] = '0';
            dfs(i  + 1, j,k);
            dfs(i , j + 1,k);
            dfs(i  -1 , j,k);
            dfs(i , j - 1,k);
        };
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid[0].size();j++)
            {
                if(grid[i][j] == '1') dfs(i,j,res++);
            }
        }
        return res - 2;
    }
};

695. 岛屿的最大面积​

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        function<int(int ,int,int)> dfs = [&](int i,int j,int k){
            if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) return 0;
            grid[i][j] = k;
            return 1 + dfs(i + 1, j , k) + dfs(i, j + 1 , k) + dfs(i - 1, j , k) + dfs(i, j - 1 , k);
        };
        int res = 0 ,  k = 1;
        for(int i = 0 ; i < grid.size();i++)
        {
            for(int j = 0; j < grid[0].size();j++)
            {
                if(grid[i][j] == 1)
                {
                    int r = dfs(i, j , ++k);
                    res = max(res, r);
                }
            }
        }
        return res;
    }
};

797. 所有可能的路径​

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path;
        function<void(int)> dfs = [&](int index)
        {
            path.push_back(index);
            if(index == graph.size() - 1)
            {
                res.push_back(path);
                return;
            }
            for(int i = 0; i < graph[index].size();i++)
            {
                dfs(graph[index][i]);
                path.pop_back();
            }
            
        };
        dfs(0);
        return res;
    }
};

934. 最短的桥​

class Solution {
    bool is_find = false;
    //感染函数，把所有 1 变为2
    void ganran(vector<vector<int>>& grid ,int i , int j ,int num)
    {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid.size()) return;
        if (grid[i][j] != 1) return;
        grid[i][j] = num;
        ganran(grid , i + 1,  j,num);
        ganran(grid , i - 1,  j,num);
        ganran(grid , i ,  j- 1,num);
        ganran(grid , i ,  j + 1,num);
    }
    //扩建函数
    void kuojian(vector<vector<int>>& grid ,int num)
    {
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid.size(); ++j) {
                if (grid[i][j] == num - 1)
                {
                    if(i > 0 && grid[i - 1][j] == 1||j > 0 && grid[i][j - 1] == 1||i <  grid.size() - 1 && grid[i + 1][j] == 1||j <  grid.size() - 1 && grid[i][j + 1] == 1)
                    {
                        is_find = true;
                        return;
                    }
                    if (i > 0 && grid[i - 1][j] == 0)grid[i - 1][j] = num;
                    if (j > 0 && grid[i][j - 1] == 0)grid[i][j - 1] = num;
                    if (i <  grid.size() - 1 && grid[i + 1][j] == 0)grid[i + 1][j] = num;
                    if (j <  grid.size() - 1 && grid[i][j + 1] == 0)grid[i][j + 1] = num;
                }
            }
        }

    }

public:
    int shortestBridge(vector<vector<int>>& grid) {
        //先找到一处为1的点 i j
        bool find = false ;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid.size(); ++j) {
                if(grid[i][j] == 1)
                {
                    //随便标记一处岛屿 2
                    ganran(grid,i,j,2);
                    find = true;
                    break;
                }
            }
            if (find) break;
        }
        //将岛屿向外面扩展 ， 每次扩展 + 1操作 ，如果遇到 1 ，那么扩展的次数就为桥梁的数
        int count = 0;
        while (!is_find)
        {
            kuojian( grid , count + 3);
            count++;
        }
        return count - 1;
    }
};

剑指 Offer 13. 机器人的运动范围​

class Solution {
    int cal(int n)
    {
        int res = 0;
        while(n)
        {
            res += n %10;
            n /= 10;
        }
        return res;
    }
public:
    int movingCount(int m, int n, int k) {
        //深搜
        int count = 0;
        vector<vector<bool>> used(m,vector<bool>(n,false));
        function<void(int,int)> dfs = [&](int i ,int j)
        {
            if(i < 0 || j < 0 || i >= m || j >= n || used[i][j]) return;
            //判断是否可行
            if(cal(i) + cal(j) > k) return;
            used[i][j] = true;
            count++;
            dfs(i + 1, j);
            dfs(i, j + 1);
        };
        dfs(0,0);
        return count;
    }
};

LCR 106. 判断二分图​

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        //染色法 {0 : 未染色 ， 1 ：红色 ， -1 ：蓝色}
        vector<int> color(graph.size(),0);
        bool res = true;
        function<void(int,int)> ran = [&](int pos ,int c){
            if(color[pos] != 0) return;
            color[pos] = c;
            for(auto x : graph[pos]) 
            {
                if(color[pos] == color[x]) res = false;
                ran(x,-c);
            }
        };
        for(int i = 0; i < graph.size();i++) ran(i, 1);
        return res;
    }
};

LCR 112. 矩阵中的最长递增路径​

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int res = 0;
        vector<vector<int>> mark(matrix.size(),vector<int>(matrix[0].size(),0));
        function<int(int , int)> dfs = [&](int i, int j){
            if(mark[i][j] != 0) return mark[i][j];
            int r = 1 ,cur = matrix[i][j];
            if(i > 0 && matrix[i - 1][j] > cur) r = max(1 + dfs(i - 1,j),r);
            if(j > 0 && matrix[i][j - 1] > cur) r = max(1 + dfs(i,j - 1),r);
            if(i < matrix.size() - 1 && matrix[i + 1][j] > cur) r =  max(1 + dfs(i + 1,j),r);
            if(j < matrix[0].size() - 1 && matrix[i][j + 1] > cur) r = max(1 + dfs(i ,j + 1),r);
            mark[i][j] = r;
            return r;
        };

        for(int i = 0; i < matrix.size() ;i++)
        {
            for(int j = 0; j < matrix[0].size() ;j++)
            {
                res = max(dfs(i,j),res);
            }
        }
        return res;
    }
};

1079. 活字印刷​

class Solution {
public:
    int numTilePossibilities(string tiles) {
        int nums[26] = {0};
        for(char x:tiles) nums[x - 'A']++;
        int res = 0;
        function<void()> dfs = [&]()
        {
            for(int j=0;j < 26;j++)
            {
                if(nums[j])
                {
                    nums[j]--;
                    res++;
                    dfs();
                    nums[j]++;
                }
            }
        };
        dfs();
        return res;
    }
    
};

面试题 16.19. 水域大小​

class Solution {
public:
    vector<int> pondSizes(vector<vector<int>>& land) {

        function<int(int ,int)> dfs = [&](int i ,int j)
        {
            if(i < 0 || j < 0 || i >= land.size() || j >= land[0].size() || land[i][j]) return 0;
            land[i][j] = 1;
            return 1 + dfs(i + 1,j)+ dfs(i,j + 1) + dfs(i + 1,j + 1) + dfs(i + 1,j - 1) + dfs(i - 1,j) + dfs(i - 1,j - 1) + dfs(i - 1,j + 1) + dfs(i,j - 1);
        };
        vector<int> res;
        for(int i = 0 ; i < land.size() ; i++)
        {
            for(int j = 0; j < land[0].size();j++)
            {
                if(land[i][j] == 0)res.push_back(dfs(i , j));
            }
        }
        sort(res.begin(),res.end());
        return res;
    }
};

417. 太平洋大西洋水流问题**​

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> visited(heights.size(),vector<int>(heights[0].size(),0));
        function<void(int, int, int)> dfs = [&](int i , int j , int pre){
            if(i < 0 || j < 0 || i >= heights.size() || j >= heights[0].size() || pre > heights[i][j] || visited[i][j] == 1) return;
            visited[i][j] = 1;
            dfs(i , j + 1, heights[i][j]);
            dfs(i , j - 1, heights[i][j]);
            dfs(i + 1, j , heights[i][j]);
            dfs(i - 1, j , heights[i][j]);
        };
        vector<vector<int>> res;
        function<void(int, int, int)> dfs2 = [&](int i , int j , int pre){
            if(i < 0 || j < 0 || i >= heights.size() || j >= heights[0].size() || pre > heights[i][j] || visited[i][j] == -1) return;
            if(visited[i][j] == 1) res.push_back({i,j});
            visited[i][j] = -1;
            dfs2(i , j + 1, heights[i][j]);
            dfs2(i , j - 1, heights[i][j]);
            dfs2(i + 1, j , heights[i][j]);
            dfs2(i - 1, j , heights[i][j]);
        };

        //左上
        for(int i = 0; i < heights.size();i++) dfs(i,0,-1);
        for(int i = 0; i < heights[0].size();i++) dfs(0,i,-1);
        /*for(int i = 0; i < visited.size();i++)
        {
            for(int j = 0; j < visited[0].size();j++)
            {
                cout << visited[i][j] << " ";
            }
            cout <<endl;
        }*/

        //右下
        for(int i = 0; i < heights.size();i++) dfs2(i,heights[0].size() - 1,-1);
        for(int i = 0; i < heights[0].size();i++) dfs2(heights.size() - 1,i,-1);
        return res;
    }
};

403. 青蛙过河***​

class Solution {
public:
    bool canCross(vector<int>& stones) {

        unordered_map<int, unordered_set<int>> visited;// 石头 ：{速度1，速度2}
        unordered_set<int> stone_pos(stones.begin(), stones.end());
        int done = stones.back();
        //dfs
        function<bool(int,int)> dfs = [&](int prv_pos, int speed){
            int cur_pos = prv_pos + speed; //现在的位置
            if(speed < 0 || !stone_pos.count(cur_pos))return false; //没有现在的位置
            if(visited[prv_pos].count(speed))return false; //石头已经访问
            visited[prv_pos].insert(speed);  //把速度加入之前的石头

            if(cur_pos == done)return true;
            
            return dfs(cur_pos, speed-1) || 
                dfs(cur_pos, speed) || dfs(cur_pos, speed+1);  
        };

        return dfs(0,1);
    }
};


1020. 飞地的数量​

//飞地数量
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        function<void(int,int)> dfs = [&](int i, int j){
            if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) return;
            grid[i][j] = 0;
            dfs(i + 1, j);
            dfs(i, j + 1);
            dfs(i - 1, j);
            dfs(i, j - 1);
        };
        for(int i = 0; i < grid.size();i++) dfs(i,0);
        for(int i = 0; i < grid[0].size();i++) dfs(0,i);
        for(int i = 0; i < grid[0].size();i++) dfs(grid.size() - 1,i);
        for(int i = 0; i < grid.size();i++) dfs(i,grid[0].size() - 1);
        int cont = 0;
        for(int i = 0; i < grid.size();i++)
        {
            cont += accumultate(grid[i].begin(),grid[i].end(),0);
        }
        return cont;
    }
};

827. 最大人工岛​

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        //遍历岛屿面积
        unordered_map<int,int> umap;
        function<int(int,int,int)> dfs = [&](int i , int j, int k){
            if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) return 0;
            int cnt = 0;
            grid[i][j] = k;
            cnt += dfs(i + 1, j , k);
            cnt += dfs(i - 1, j , k);
            cnt += dfs(i, j + 1 , k);
            cnt += dfs(i, j - 1 , k);
            return cnt + 1;
        };
        int k = 2 , res = 0;
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j] == 1) 
                {
                    umap[k] = dfs(i , j ,k);
                    res = max(umap[k],res);
                    k++;
                }
            }
        }
        
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j] == 0) 
                {
                    unordered_set<int> uset;
                    int cnt = 1;
                    if(i - 1 >= 0 && grid[i - 1][j]) uset.insert(grid[i - 1][j]);
                    if(j - 1 >= 0 && grid[i][j - 1]) uset.insert(grid[i][j - 1]);
                    if(i + 1 < grid.size() && grid[i + 1][j]) uset.insert(grid[i + 1][j]);
                    if(j + 1 < grid[0].size() && grid[i][j + 1]) uset.insert(grid[i][j + 1]);
                    for(int x : uset) cnt += umap[x];
                    res = max(res,cnt);
                }
            }
        }
        return res;
    }
};

广度优先搜索​

127. 单词接龙​

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(),wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;
        unordered_map<string,int> wordDict;
        wordDict[beginWord] = 1;
        queue<string> que;
        que.push(beginWord);
        while(!que.empty())
        {
            string now = que.front();
            que.pop();
            for(int i = 0; i < now.size();i++)
            {
                string now_stru = now;
                for(char ch = 'a'; ch <= 'z' ;ch++)
                {
                    now_stru[i] = ch;
                    if(now_stru == endWord) return wordDict[now] + 1;
                    if(ch != now[i] && wordSet.find(now_stru) != wordSet.end() && wordDict.find(now_stru) == wordDict.end())
                    {
                        wordDict[now_stru] = wordDict[now] + 1;
                        que.push(now_stru);
                    }
                }
            }
        }
        return 0;
    }
};

130. 被围绕的区域​

class Solution {

public:
    void solve(vector<vector<char>>& board) {

        function<void(int,int)> ganran = [&](int i,int j)
        {
            if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != 'O') return;
        board[i][j] = 'P';
        ganran( i + 1,  j);
        ganran(i - 1,  j);
        ganran(i ,  j- 1);
        ganran(i ,  j + 1);
        };
        for(int i = 0; i < board[0].size();i++)
        {
            if(board[0][i] == 'O') ganran(0,i);
            if(board.back()[i] == 'O') ganran(board.size() - 1,i);
        }
        for(int i = 0; i < board.size();i++)
        {
            if(board[i][0] == 'O') ganran(i,0);
            if(board[i][board[0].size() - 1] == 'O') ganran(i,board[0].size() - 1);
        }
        for(int i = 0; i < board.size();i++)
        {
            for(int j = 0; j < board[0].size();j++)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        for(int i = 0; i < board.size();i++)
        {
            for(int j = 0; j < board[0].size();j++)
            {
                if(board[i][j] == 'P') board[i][j] = 'O';
            }
        }
    }
};

LCR 109. 打开转盘锁​

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> uset(deadends.begin(),deadends.end());
        if(uset.find(target) != uset.end() || uset.find("0000") != uset.end()) return -1;
        //8种状态的广度优先搜索
        queue<string> que;
        unordered_set<string> used;
        que.push("0000");
        used.insert("0000");
        int step = 0;
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                string top  = que.front();
                if(top == target) return step;
                que.pop();
                for(int i = 0 ; i < 4 ;i++)
                {
                    char ch = top[i];
                    char ch1 = (ch - '0' + 1) % 10 + '0';
                    char ch2 = (ch - '0' - 1 + 10) % 10 + '0';
                    top[i] = ch1;
                    if(uset.find(top) == uset.end() && used.find(top) == used.end()) 
                    {
                        que.push(top);
                        used.insert(top);
                    }
                    top[i] = ch2;
                    if(uset.find(top) == uset.end() && used.find(top) == used.end()) 
                    {
                        que.push(top);
                        used.insert(top);
                    }
                    top[i] = ch;
                }
            }
            step++;
        }
        return -1;
    }
};

1926. 迷宫中离入口最近的出口​

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        // 思路：从入口开始按轮BFS，遇到邻居为“.”则入队，并记录轮数
        // 结束条件时，邻居为边缘格子，返回轮数
        // 若BFS结束也没有找到出口，返回-1

        const int m = maze.size();
        const int n = maze[0].size();
        const int dr[4] = {0, 0, 1, -1};
        const int dc[4] = {1, -1, 0, 0};
        queue<pair<int, int>> que;

        // 初始化
        int erow = entrance[0], ecol = entrance[1];
        que.emplace(erow, ecol);
        maze[erow][ecol] = '-';  // 表示已经搜索过

        // 按轮BFS
        int epoch = 0;
        while (!que.empty()) {
            int counter = que.size();
            epoch++;
            // 一轮
            for (int k = 0; k < counter; k++) {
                auto [r, c] = que.front();
                que.pop();
                // 邻居找'.'入队
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') {
                        // 是边沿直接返回
                        if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) return epoch;
                        // 不是边沿，入队
                        maze[nr][nc] = '-';  // 表示已经搜过
                        que.emplace(nr, nc); 
                    }
                }
            }

        }
        return -1;

    }
};

815. 公交路线***​

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target) return 0;
        //umap[site] -> 保存去那一辆公交车
        unordered_map<int , vector<int>> umap;
        for(int i = 0; i < routes.size() ;i++)
        {
            for(int site : routes[i])
            {
                umap[site].push_back(i);
            }
        }
        vector<bool> used(routes.size(),false);
        queue<int> que;
        que.push(source);
        int count = 0;
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                int front = que.front();
                que.pop();
                if(front == target) return count;
                //搭乘对应的公交车
                for(int bus : umap[front])
                {
                    if(used[bus]) continue;
                    used[bus] = true;
                    for(int i : routes[bus])
                    {
                        que.push(i);
                    }
                }
            }
            count++;
        }
        return -1;
    }
};

1091. 二进制矩阵中的最短路径*​

有个坑的地方 卡了好久 push 之后要置为1

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0] != 0 || grid.back().back() != 0) return -1;
        queue<pair<int,int>> que;
        que.push(pair<int,int>(0,0));
        int count = 1;
        //vector<vector<bool>> used(grid.size(),vector<bool>(grid[0].size(),false));
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                
                pair<int,int> front = que.front();
                que.pop();
                int n = grid.size(),i = front.first,j = front.second;
                if(i == n - 1 && j == n - 1) return count;

                for(int m = -1; m <= 1; m++)
                {
                    for(int k = -1; k <= 1; k++)
                    {
                        if(m == 0 && k == 0) continue;
                        int newi = i + m , newj = j + k;
                        if(newi < 0|| newi >= n|| newj < 0|| newj >= n || grid[newi][newj]) continue;
                        que.push({newi,newj});
                        grid[newi][newj] = 1; //push 之后要置为1
                    }
                }
            }
            count++;
        }
        return -1;
    }
};

1293. 网格中的最短路径***​

class Solution {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        //使用DFS ，增加一个维度 ， 代表这个节点已经使用过的 k 次数
        if(k >= grid.size() + grid[0].size() - 3) return grid.size() + grid[0].size() - 2;
        queue<vector<int>> que;
        que.push({0,0,k});
        int count = 0;
        vector<vector<vector<bool>>> visited(grid.size(), vector<vector<bool>>(grid[0].size(), vector<bool>(k + 1, false)));

        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                vector<int> front = que.front();
                que.pop();
                int i = front[0] , j = front[1] , num = front[2];
                if(i == grid.size() - 1 && j == grid[0].size() - 1 && num >= 0) return count;
                if(visited[i][j][num]) continue;
                visited[i][j][num] = true;

                for(int m = 0; m < 4; m++)
                {
                    int newi = i + dx[m] , newj = j + dy[m];
                    if(newi < 0 || newi >= grid.size() || newj < 0 ||newj >= grid[0].size()) continue;
                    
                    if(grid[newi][newj] == 1 && num >= 1) que.push({newi,newj,num - 1});
                    else if(grid[newi][newj] == 0) que.push({newi,newj,num});
                }
            }
            count++;
        }
        return -1;
    }
};

863. 二叉树中所有距离为 K 的结点**​

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        
        //存储父子节点
        unordered_map<TreeNode* ,vector<TreeNode*>> umap;
        function<void(TreeNode*)> search = [&](TreeNode* root){
            if(!root) return;
            if(root->left)
            {
                umap[root->left].push_back(root);
                umap[root].push_back(root->left);
                search(root->left);
            }
            if(root->right)
            {
                umap[root->right].push_back(root);
                umap[root].push_back(root->right);
                search(root->right);
            }
        };
        search(root);

        //BFS
        queue<TreeNode*> que;
        unordered_set<TreeNode*> visited;
        vector<int> res;
        que.push(target);
        int count = 0;
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                TreeNode* top = que.front();
                que.pop();
                visited.insert(top);
                if(count == k)
                {
                    res.push_back(top->val);
                }
                else
                {
                    for(auto x : umap[top])
                        if(visited.find(x) == visited.end()) que.push(x);
                }
            }
            count++;
        }
        return res;
    }
};

1654. 到家的最少跳跃次数​

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        const int mx = 6000;
        unordered_set<int> forbidSet(forbidden.begin(),forbidden.end());
        array<array<bool,2>,mx> umap = {};
        queue<pair<int,int>> que;
        que.push(pair<int,int>(0,0));
        int count = 0;
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                pair<int,int> cur = que.front();
                que.pop();
                if(cur.first == x) return count;
                if(umap[cur.first][cur.second]) continue;
                umap[cur.first][cur.second] = true;
                
                if(cur.first + a < mx && forbidSet.find(cur.first + a) == forbidSet.end() && !umap[cur.first + a][0]) 
                 {
                    que.push(pair<int,int>(cur.first + a,0));
                 }
                if(cur.first - b > 0 && cur.second == 0 && forbidSet.find(cur.first - b) == forbidSet.end() && !umap[cur.first - b][1]) 
                 {
                    que.push(pair<int,int>(cur.first - b,1));
                 }
            }
            count++;
        }
        return -1;
    }
};

并查集​

684. 冗余连接​

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int father[1001] = {0};
        for(int i = 0; i <= 1000; i++) father[i] = i;
        function<int(int)> find = [&](int n)
        {
            return n == father[n] ? n : father[n] = find(father[n]);
        };
        function<void(int,int)> uni = [&](int a, int b)
        {
            int fa = find(a);
            int fb = find(b);
            if(fa == fb) return;
            father[fa] = fb;
        };
        for(int i = 0; i < edges.size();i++)
        {
            if(find(edges[i][0]) != find(edges[i][1]) ) uni(edges[i][0],edges[i][1]);
            else return edges[i];
        }
        return {};
    }
};

547. 省份数量​

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int father[201] = {0};
        for(int i = 0; i < 201;i++) father[i] = i;
        function<int(int)> find = [&](int n)
        {
            return n == father[n] ? n : father[n] = find(father[n]);
        };
        function<void(int,int)> uni = [&](int a, int b)
        {
            int fa = find(a);
            int fb = find(b);
            if(fa == fb) return;
            father[fa] = fb;
        };
        unordered_set<int> res;
        for(int i = 0; i < isConnected.size();i++)
        {
            for(int j = i + 1; j < isConnected[0].size();j++)
            {
                if(isConnected[i][j])uni(i,j);
            }
        }
        for(int i = 0;i < isConnected.size();i++) 
        {
            res.insert(find(i));
        }
        return res.size();
    }
};

LCR 117. 相似字符串组​

class Solution {
    int father[300];
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
    bool isy(string a , string b)
    {
        if(a.size() != b.size()) return false;
        if(a == b) return true;
        int pos1 = -1,pos2 = -1;
        for(int i = 0 ; i < a.size();i++)
        {
            if(a[i] != b[i]) 
            {
                if(pos1 == -1) pos1 = i;
                else{
                    pos2 = i;
                    break;
                }
            }
        }
        if(pos2 == -1) return false;
        swap(a[pos1],a[pos2]);
        //cout << a <<","<< b <<endl;
        return a == b;
    }
public:
    int numSimilarGroups(vector<string>& strs) {
        for(int i = 0; i < 300;i++) father[i] = i;
        for(int i = 0 ; i < strs.size();i++)
            for(int j = i + 1; j < strs.size();j++)
                if(isy(strs[i],strs[j])) 
                {
                    //cout << strs[i]<<","<<strs[j]<<endl;
                    join(i,j);
                }
        unordered_set<int> uset;
        for(int i = 0; i < strs.size();i++) uset.insert(find(i));
        return uset.size();
    }
};