图论 | Bo Peng

DFS

深度优先搜索(DFS)是对图进行遍历的基本方法，它等同于前面介绍过的回溯。因此DFS算法的基本框架可参考回溯模板如下。

 def dfs(节点，参数):
    if 终止条件:
        存放结果
        return
    
    for (选择：与节点相邻的其它节点):
        处理节点
        dfs(选择的节点)
        回溯(撤销对节点的处理)
 

797. 所有可能的路径

给你一个有n个节点的有向无环图(DAG)，请你找出所有从节点0到节点n-1的路径并输出(不要求按特定顺序)。

graph[i]是一个从节点i可以访问的所有节点的列表(即从节点i到节点graph[i][j]存在一条有向边)。

示例1：

 输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
 

示例2：

 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
 

提示：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (即不存在自环)
graph[i]中的所有元素互不相同
保证输入为有向无环图(DAG)

Solution

本题需要使用DFS来遍历起点0到终点n-1的所有路径，当到达终点n-1时将路径path添加到结果res中即可。

题目链接：

python代码：

 class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        N = len(graph)

        path = [0]
        res = []

        def dfs(node: int) -> None:
            nonlocal path, res
            
            if node == N-1:
                res.append(path[:])
                return
            
            for v in graph[node]:
                path.append(v)
                dfs(v)
                path.pop()
        
        dfs(0)

        return res
 

C++代码：

 class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.clear();
        res.clear();

        path.push_back(0);
        dfs(graph, 0);

        return res;
    }

private:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(vector<vector<int>>& graph, int x) {
        if (x == graph.size()-1) {
            res.push_back(path);
            return;
        }

        for (int i=0; i<graph[x].size(); ++i) {
            path.push_back(graph[x][i]);
            dfs(graph, graph[x][i]);
            path.pop_back();
        }
    }
};
 

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
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]的值为'0'或'1'

Solution

本题的解法在于对整个地图进行遍历，每遇到一个岛屿就对所有和它相连的陆地进行标记并令岛屿记数res加1。本题的DFS解法可参考如下。

题目链接：

python代码：

 class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        H = len(grid)
        W = len(grid[0])

        visited = [[0 for j in range(W)] for i in range(H)]
        res = 0

        def dfs(x: int, y: int) -> None:
            nonlocal visited

            visited[y][x] = 1
            
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if 0 <= x+dx < W and 0 <= y+dy < H and grid[y+dy][x+dx] == '1' and not visited[y+dy][x+dx]:
                    dfs(x+dx, y+dy)
        
        for y in range(H):
            for x in range(W):
                if grid[y][x] == '1' and not visited[y][x]:
                    dfs(x, y)
                    res += 1
            
        return res
 

C++代码：

 class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        vector<vector<bool>> visited = vector<vector<bool>>(H, vector<bool>(W, false)); 
        int res = 0;

        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == '1' && !visited[x][y]) {
                    dfs(grid, visited, x, y);
                    ++res;
                }
            }
        }

        return res;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        visited[x][y] = true;

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
            if (grid[xx][yy] == '1' && !visited[xx][yy]) dfs(grid, visited, xx, yy);
        }
    }
};
 

695. 岛屿的最大面积

给你一个大小为m x n的二进制矩阵grid。

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

岛屿的面积是岛上值为1的单元格的数目。

计算并返回grid中最大的岛屿面积。如果没有岛屿，则返回面积为0。

示例1：

 输入：grid = [[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 。
 

示例2：

 输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]的值为0或1

Solution

本题的解法类似于岛屿数量，不过在DFS过程中需要把当前岛屿的面积记录在变量A中并且对所有的岛屿面积取最大值。

题目链接：

python代码：

 class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        visited = [[0 for j in range(N)] for i in range(M)]
        res = A = 0

        def dfs(x: int, y: int) -> None:
            nonlocal visited, A

            visited[y][x] = 1
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if 0 <= y+dy < M and 0 <= x+dx < N and grid[y+dy][x+dx] and not visited[y+dy][x+dx]:
                    A += 1
                    dfs(x+dx, y+dy)
            
        
        for y in range(M):
            for x in range(N):
                if grid[y][x] and not visited[y][x]:
                    A = 1
                    dfs(x, y)
                    res = max(res, A)
        
        return res
 

C++代码：

 class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        vector<vector<bool>> visited = vector<vector<bool>>(H, vector<bool>(W, false)); 
        int res = 0;

        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == 1 && !visited[x][y]) {
                    A = 0;
                    dfs(grid, visited, x, y);
                    res = max(res, A);
                }
            }
        }

        return res;
    }

private:
    int A;
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        visited[x][y] = true;
        ++A;

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
            if (grid[xx][yy] == 1 && !visited[xx][yy]) dfs(grid, visited, xx, yy);
        }
    }
};
 

1020. 飞地的数量

给你一个大小为m x n的二进制矩阵grid，其中0表示一个海洋单元格、1表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过grid的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例1：

 输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 

示例2：

 输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j]的值为0或1

Solution

本题的难点在于如何判断一块岛屿是否是飞地。实际上我们可以先从grid的四条边出发把所有和边相连的岛屿(绿色)都修改成海洋，这样grid剩余的岛屿(黄色)就都是飞地了。本题的DFS解法可参考如下。

题目链接：

python代码：

 class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        res = 0

        def dfs(x: int, y: int) -> None:
            nonlocal grid, res

            grid[y][x] = 0
            res += 1

            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if 0 <= y+dy < M and 0 <= x+dx < N and grid[y+dy][x+dx]:
                    dfs(x+dx, y+dy)
        
        for y in range(M):
            if grid[y][0]:
                dfs(0, y)
            if grid[y][N-1]:
                dfs(N-1, y)
        
        for x in range(N):
            if grid[0][x]:
                dfs(x, 0)
            if grid[M-1][x]:
                dfs(x, M-1)
        
        res = 0
        for y in range(M):
            for x in range(N):
                if grid[y][x]:
                    dfs(x, y)

        return res
 

C++代码：

 class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        for (int i=0; i<H; ++i) {
            if (grid[i][0] == 1) dfs(grid, i, 0);
            if (grid[i][W-1] == 1) dfs(grid, i, W-1);
        }

        for (int j=0; j<W; ++j) {
            if (grid[0][j] == 1) dfs(grid, 0, j);
            if (grid[H-1][j] == 1) dfs(grid, H-1, j);
        }

        count = 0;
        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == 1) dfs(grid, x, y);
            }
        }

        return count;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    int count;

    void dfs(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = 0;
        ++count;

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
            if (grid[xx][yy] == 1) dfs(grid, xx, yy);
        }
    }
};
 

130. 被围绕的区域

给你一个m x n的矩阵board，由若干字符'X'和'O'，找到所有被'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。

示例1：

 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 

示例2：

 输入：board = [["X"]]
输出：[["X"]]
 

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]为'X'或'O'

Solution

本题的解法类似于飞地的数量。我们只需要先标记board中与边界相连的岛屿，然后对board进行遍历把所有未标记过的岛屿到填充为'X'即可。本题的DFS解法可参考如下。

题目链接：

 class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        M = len(board)
        N = len(board[0])

        visited = [[0 for j in range(N)] for i in range(M)]

        def dfs(x: int, y: int) -> None:
            nonlocal visited

            visited[y][x] = 1
            
            for dx, dy in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                if 0 <= y+dy < M and 0 <= x+dx < N and board[y+dy][x+dx] == "O" and not visited[y+dy][x+dx]:
                    dfs(x+dx, y+dy)
        
        for y in range(M):
            if board[y][0] == "O":
                dfs(0, y)
            
            if board[y][N-1] == "O":
                dfs(N-1, y)
        
        for x in range(N):
            if board[0][x] == "O":
                dfs(x, 0)
            
            if board[M-1][x] == "O":
                dfs(x, M-1)
        
        for y in range(M):
            for x in range(N):
                if board[y][x] == "O" and not visited[y][x]:
                    board[y][x] = "X"
 

C++代码：

 class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int M = board.size();
        int N = board[0].size();

        for (int i=0; i<M; ++i) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][N-1] == 'O') dfs(board, i, N-1);
        }

        for (int j=0; j<N; ++j) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[M-1][j] == 'O') dfs(board, M-1, j);
        }

        for (int i=0; i<M; ++i) {
            for (int j=0; j<N; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }

    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void dfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = 'A';

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= board.size() || yy < 0 || yy >= board[0].size()) continue;
            if (board[xx][yy] == 'X' || board[xx][yy] == 'A') continue;
            
            dfs(board, xx, yy);
        }
    }
};
 

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

有一个m × n的矩形岛屿，与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个m x n的整数矩阵heights，heights[r][c]表示坐标(r, c)上单元格高于海平面的高度。

岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标result的2D 列表，其中result[i] = [ri, ci]表示雨水从单元格(ri, ci)流动既可流向太平洋也可流向大西洋。

示例1：

 输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
 

示例2：

 输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
 

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10⁵

Solution

本题的直接解法是对网格中的每一个位置进行遍历，如果它能够同时流向太平洋和大西洋则将其加入到res中。然而这样的直接解法的复杂度为O(m²n²)，会出现超时的问题。

因此本题中我们需要从反方向进行思考。假设水流可以从太平洋和大西洋按高度逆流到网格中，如果某个位置能够同时接收到两个方向的水流则将它加入到res中。从这样的角度我们只需要对网格的四边进行遍历，标记那些能够接收到来自太平洋和大西洋水流的节点即可。优化后的算法复杂度为O(mn)，其DFS实现可以参考如下。

题目链接：

python代码：

 class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        M = len(heights)
        N = len(heights[0])

        visited = [[[0, 0] for j in range(N)] for i in range(M)]
        res = []

        def dfs(r: int, c: int, src: int) -> None:
            nonlocal visited
            
            for dr, dc in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                rr = r + dr
                cc = c + dc

                if 0 <= rr < M and 0 <= cc < N and heights[rr][cc] >= heights[r][c] and not visited[rr][cc][src]:
                    visited[rr][cc][src] = 1
                    dfs(rr, cc, src)
        
        for r in range(M):
            visited[r][0][0] = 1
            visited[r][N-1][1] = 1

            dfs(r, 0, 0)
            dfs(r, N-1, 1)
        
        for c in range(N):
            visited[0][c][0] = 1
            visited[M-1][c][1] = 1

            dfs(0, c, 0)
            dfs(M-1, c, 1)
        
        for r in range(M):
            for c in range(N):
                if visited[r][c][0] and visited[r][c][1]:
                    res.append([r, c])
        
        return res
 

C++代码：

 class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int H = heights.size();
        int W = heights[0].size();

        vector<vector<int>> res;

        vector<vector<bool>> pacific  = vector<vector<bool>>(H, vector<bool>(W, false));
        vector<vector<bool>> atlantic = vector<vector<bool>>(H, vector<bool>(W, false));

        for (int i=0; i<H; ++i) {
            dfs(heights, pacific, i, 0);
            dfs(heights, atlantic, i, W-1);
        }

        for (int j=0; j<W; ++j) {
            dfs(heights, pacific, 0, j);
            dfs(heights, atlantic, H-1, j);
        }

        for (int i=0; i<H; ++i) {
            for (int j=0; j<W; ++j) {
                if (pacific[i][j] && atlantic[i][j]) res.push_back({i, j});
            }
        }

        return res;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
        if (visited[x][y]) return;

        visited[x][y] = true;

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= heights.size() || yy < 0 || yy >= heights[0].size()) continue;
            if (heights[xx][yy] < heights[x][y]) continue;

            dfs(heights, visited, xx, yy);
        }
    }
};
 

827. 最大人工岛

给你一个大小为n x n二进制矩阵grid。最多只能将一格0变成1。

返回执行此操作后，grid中最大的岛屿面积是多少？

岛屿由一组上、下、左、右四个方向相连的1形成。

示例1：

 输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
 

示例2：

 输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
 

示例3：

 输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
 

提示：

n == grid.length
n == grid[r].length
1 <= n <= 500
grid[i][j]为0或1

Solution

本题的暴力解法是尝试将grid中每个海洋单元格修改为1然后计算此时的最大岛屿面积。显然这种做法有过高的时间复杂度，会直接导致超时。

因此本题的解法在于对grid进行两次遍历。在第一次遍历中记录下每个岛屿的面积，而在第二次遍历中尝试将原来的海洋单元格修改为陆地并累加所有和它相连的不同岛屿面积。本题的DFS解法可参考如下。

题目链接：

python代码：

 class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)

        visited = [[0 for j in range(N)] for i in range(N)]

        As = {}
        Amax = 0

        def dfs(x: int, y: int, label: int) -> None:
            nonlocal visited, A

            visited[y][x] = label
            A += 1

            for dx, dy in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                xx = x + dx
                yy = y + dy

                if 0 <= yy < N and 0 <= xx < N and grid[yy][xx] and not visited[yy][xx]:
                    dfs(xx, yy, label)

        ## first loop
        for y in range(N):
            for x in range(N):
                if grid[y][x] and not visited[y][x]:
                    A = 0
                    label = len(As)+1

                    dfs(x, y, label)
                    As[label] = A
                    Amax = max(Amax, A)
        
        ## second loop
        for y in range(N):
            for x in range(N):
                if not visited[y][x]:
                    A = 1
                    connect = []

                    for dx, dy in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                        xx = x + dx
                        yy = y + dy

                        if 0 <= yy < N and 0 <= xx < N and visited[yy][xx] and visited[yy][xx] not in connect:
                            A += As[visited[yy][xx]]
                            connect.append(visited[yy][xx])
                    
                    Amax = max(Amax, A)

        return Amax
 

C++代码：

 class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        unordered_map<int, int> As;
        vector<vector<bool>> visited = vector<vector<bool>>(H, vector<bool>(W, false));
        int mark = 2;

        // first loop
        for (int i=0; i<H; ++i) {
            for (int j=0; j<W; ++j) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, visited, i, j, mark);
                    As[mark] = count;
                    ++mark;
                }
            }
        }

        // second loop
        int res = As[2];
        for (int i=0; i<H; ++i) {
            for (int j=0; j<W; ++j) {
                if (grid[i][j] == 0) {
                    int A = 1;
                    set<int> connect;

                    for (int k=0; k<4; ++k) {
                        int x = i + dirs[k][0];
                        int y = j + dirs[k][1];

                        if (x < 0 || x >= H || y < 0 || y >= W) continue;
                        connect.insert(grid[x][y]);
                    }

                    for (int mark : connect) A += As[mark];
                    res = max(res, A);
                }
            }
        }

        return res;
    }

private:
    int count;
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {
        if (grid[x][y] == 0 || visited[x][y]) return;

        visited[x][y] = true;
        grid[x][y]    = mark;

        ++count;

        for (int i=0; i<4; ++i) {
            int xx = x + dirs[i][0];
            int yy = y + dirs[i][1];

            if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;

            dfs(grid, visited, xx, yy, mark);
        }
    }
};
 

841. 钥匙和房间

有n个房间，房间按从0到n - 1编号。最初，除0号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组rooms其中rooms[i]是你进入i号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回false。

示例1：

 输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
 

示例2：

 输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
 

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有rooms[i]的值互不相同

Solution

本题的实质是对有向图进行遍历：我们如果能从0节点出发遍历图上所有的其它节点则返回True，否则返回False。本题的DFS解法可以参考如下。

题目链接：

python代码：

 class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        N = len(rooms)
        visited = {i: 0 for i in range(N)}

        def dfs(room: int) -> None:
            nonlocal visited

            visited[room] = 1

            for key in rooms[room]:
                if not visited[key]:
                    dfs(key)
        
        dfs(0)

        for k, v in visited.items():
            if not v:
                return False
        
        return True
 

C++代码：

 class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int N = rooms.size();
        vector<bool> visited(N, false);

        dfs(rooms, visited, 0);

        for (int i=0; i<N; ++i) {
            if (!visited[i]) return false;
        }
        
        return true;
    }

private:
    void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int key) {
        if (visited[key]) return;

        visited[key] = true;
        for (int k : rooms[key]) {
            dfs(rooms, visited, k);
        }
    }
};
 

BFS

广度优先搜索(BFS)的实现类似于层序遍历。在BFS中我们需要使用一个队列来依次保存需要拓展的节点，当队列非空时弹出新的节点进行拓展。

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
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]的值为'0'或'1'

Solution

本题的BFS解法可参考如下。需要注意的是BFS在实现时每当有节点入队就将其标记为visited，否则会出现很多节点多次加入队列的情况从而导致超时。

题目链接：

python代码：

 class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        H = len(grid)
        W = len(grid[0])

        visited = [[0 for j in range(W)] for i in range(H)]
        res = 0

        def bfs(x: int, y: int) -> None:
            from collections import deque

            nonlocal visited
            
            visited[y][x] = 1
            queue = deque([(x, y)])

            while queue:
                x, y = queue.popleft()
            
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    if 0 <= x+dx < W and 0 <= y+dy < H and grid[y+dy][x+dx] == '1' and not visited[y+dy][x+dx]:
                        queue.append((x+dx, y+dy))
                        visited[y+dy][x+dx] = 1
        
        for y in range(H):
            for x in range(W):
                if grid[y][x] == '1' and not visited[y][x]:
                    bfs(x, y)
                    res += 1
            
        return res
 

C++代码：

 class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        vector<vector<bool>> visited = vector<vector<bool>>(H, vector<bool>(W, false)); 
        int res = 0;

        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == '1' && !visited[x][y]) {
                    bfs(grid, visited, x, y);
                    ++res;
                }
            }
        }

        return res;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<pair<int, int>> que;
        que.push({x, y});

        visited[x][y] = true;

        while (!que.empty()) {
            pair<int, int> cur = que.front(); que.pop();
            int curx = cur.first;
            int cury = cur.second;

            for (int i=0; i<4; ++i) {
                int xx = curx + dirs[i][0];
                int yy = cury + dirs[i][1];

                if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
                if (grid[xx][yy] == '1' && !visited[xx][yy]) {
                    visited[xx][yy] = true;
                    que.push({xx, yy});
                }
            }
        }
    }
};
 

695. 岛屿的最大面积

给你一个大小为m x n的二进制矩阵grid。

岛屿的面积是岛上值为1的单元格的数目。

计算并返回grid中最大的岛屿面积。如果没有岛屿，则返回面积为0。

示例1：

 输入：grid = [[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 。
 

示例2：

 输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]的值为0或1

Solution

本题的解法类似于岛屿数量，不过在BFS过程中需要把当前岛屿的面积记录在变量A中并且对所有的岛屿面积取最大值。

题目链接：

python代码：

 class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        visited = [[0 for j in range(N)] for i in range(M)]
        res = 0

        def bfs(x: int, y: int) -> int:
            from collections import deque

            queue = deque([(x, y)])
            A = 1

            nonlocal visited
            visited[y][x] = 1

            while queue:
                x, y = queue.popleft()

                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    if 0 <= y+dy < M and 0 <= x+dx < N and grid[y+dy][x+dx] and not visited[y+dy][x+dx]:
                        queue.append((x+dx, y+dy))
                        visited[y+dy][x+dx] = 1

                        A += 1
            
            return A     
        
        for y in range(M):
            for x in range(N):
                if grid[y][x] and not visited[y][x]:
                    A = bfs(x, y)
                    res = max(res, A)
        
        return res
 

C++代码：

 class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        vector<vector<bool>> visited = vector<vector<bool>>(H, vector<bool>(W, false)); 
        int res = 0;

        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == 1 && !visited[x][y]) {
                    A = 0;
                    bfs(grid, visited, x, y);
                    res = max(res, A);
                }
            }
        }

        return res;
    }

private:
    int A;
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<pair<int, int>> que;
        que.push({x, y});
        
        visited[x][y] = true;
        ++A;

        while (!que.empty()) {
            pair<int, int> cur = que.front(); que.pop();

            int curx = cur.first;
            int cury = cur.second;

            for (int i=0; i<4; ++i) {
                int xx = curx + dirs[i][0];
                int yy = cury + dirs[i][1];

                if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
                if (grid[xx][yy] == 1 && !visited[xx][yy]){
                    visited[xx][yy] = true;
                    que.push({xx, yy});

                    ++A;
                }
            }
        }
    }
};
 

1020. 飞地的数量

给你一个大小为m x n的二进制矩阵grid，其中0表示一个海洋单元格、1表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过grid的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例1：

 输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 

示例2：

 输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j]的值为0或1

Solution

本题的BFS解法可参考如下。

题目链接：

python代码：

 class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        res = 0

        def bfs(x: int, y: int) -> None:
            from collections import deque

            nonlocal grid, res

            queue = deque([(x, y)])
            grid[y][x] = 0
            res += 1

            while queue:
                x, y = queue.popleft()

                for dx, dy in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                    if 0 <= y+dy < M and 0 <= x+dx < N and grid[y+dy][x+dx]:
                        queue.append((x+dx, y+dy))
                        
                        grid[y+dy][x+dx] = 0
                        res += 1
        
        for y in range(M):
            if grid[y][0]:
                bfs(0, y)
            
            if grid[y][N-1]:
                bfs(N-1, y)
        
        for x in range(N):
            if grid[0][x]:
                bfs(x, 0)
            
            if grid[M-1][x]:
                bfs(x, M-1)
        
        res = 0
        for y in range(M):
            for x in range(N):
                if grid[y][x]:
                    bfs(x, y)
            
        return res
 

C++代码：

 class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int H = grid.size();
        int W = grid[0].size();

        for (int i=0; i<H; ++i) {
            if (grid[i][0] == 1) bfs(grid, i, 0);
            if (grid[i][W-1] == 1) bfs(grid, i, W-1);
        }

        for (int j=0; j<W; ++j) {
            if (grid[0][j] == 1) bfs(grid, 0, j);
            if (grid[H-1][j] == 1) bfs(grid, H-1, j);
        }

        count = 0;
        for (int x=0; x<H; ++x) {
            for (int y=0; y<W; ++y) {
                if (grid[x][y] == 1) bfs(grid, x, y);
            }
        }

        return count;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    int count;

    void bfs(vector<vector<int>>& grid, int x, int y) {
        queue<pair<int, int>> que;
        que.push({x, y});

        grid[x][y] = 0;
        ++count;

        while (!que.empty()) {
            pair<int, int> cur = que.front(); que.pop();

            int curx = cur.first;
            int cury = cur.second;

            for (int i=0; i<4; ++i) {
                int xx = curx + dirs[i][0];
                int yy = cury + dirs[i][1];

                if (xx < 0 || xx >= grid.size() || yy < 0 || yy >= grid[0].size()) continue;
                if (grid[xx][yy] == 1) {
                    grid[xx][yy] = 0;
                    que.push({xx, yy});

                    ++count;
                }
            }
        }
    }
};
 

130. 被围绕的区域

给你一个m x n的矩阵board，由若干字符'X'和'O'，找到所有被'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。

示例1：

 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 

示例2：

 输入：board = [["X"]]
输出：[["X"]]
 

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]为'X'或'O'

Solution

本题的BFS解法可参考如下。

题目链接：

python代码：

 class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        M = len(board)
        N = len(board[0])

        visited = [[0 for j in range(N)] for i in range(M)]

        def bfs(x: int, y: int) -> None:
            from collections import deque

            nonlocal visited

            visited[y][x] = 1

            queue = deque([(x, y)])

            while queue:
                x, y = queue.popleft()

                for dx, dy in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                    if 0 <= y+dy < M and 0 <= x+dx < N and board[y+dy][x+dx] == "O" and not visited[y+dy][x+dx]:
                        visited[y+dy][x+dx] = 1

                        queue.append((x+dx, y+dy))

        for y in range(M):
            if board[y][0] == "O":
                bfs(0, y)
            
            if board[y][N-1] == "O":
                bfs(N-1, y)
        
        for x in range(N):
            if board[0][x] == "O":
                bfs(x, 0)
            
            if board[M-1][x] == "O":
                bfs(x, M-1)
        
        for y in range(M):
            for x in range(N):
                if board[y][x] == "O" and not visited[y][x]:
                    board[y][x] = "X"
 

C++代码：

 class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int M = board.size();
        int N = board[0].size();

        for (int i=0; i<M; ++i) {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][N-1] == 'O') bfs(board, i, N-1);
        }

        for (int j=0; j<N; ++j) {
            if (board[0][j] == 'O') bfs(board, 0, j);
            if (board[M-1][j] == 'O') bfs(board, M-1, j);
        }

        for (int i=0; i<M; ++i) {
            for (int j=0; j<N; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }

    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    void bfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = 'A';

        queue<pair<int, int>> que;
        que.push({x, y});

        while (!que.empty()) {
            pair<int, int> cur = que.front(); que.pop();

            int curx = cur.first;
            int cury = cur.second;

            for (int i=0; i<4; ++i) {
                int xx = curx + dirs[i][0];
                int yy = cury + dirs[i][1];

                if (xx < 0 || xx >= board.size() || yy < 0 || yy >= board[0].size()) continue;
                if (board[xx][yy] == 'X' || board[xx][yy] == 'A') continue;

                board[xx][yy] = 'A';
                que.push({xx, yy});
            }
        }
    }
};
 

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

有一个m × n的矩形岛屿，与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个m x n的整数矩阵heights，heights[r][c]表示坐标(r, c)上单元格高于海平面的高度。

返回网格坐标result的2D 列表，其中result[i] = [ri, ci]表示雨水从单元格(ri, ci)流动既可流向太平洋也可流向大西洋。

示例1：

 输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
 

示例2：

 输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
 

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10⁵

Solution

本题的BFS实现可以参考如下。

题目链接：

python代码：

 class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        M = len(heights)
        N = len(heights[0])

        visited = [[[0, 0] for j in range(N)] for i in range(M)]
        res = []

        def bfs(r: int, c: int, src: int) -> None:
            from collections import deque

            queue = deque([(r, c)])

            nonlocal visited

            visited[r][c][src] = 1

            while queue:
                r, c = queue.popleft()

                for dr, dc in [(0, 1), (0,-1), (1, 0), (-1, 0)]:
                    rr = r + dr
                    cc = c + dc

                    if 0 <= rr < M and 0 <= cc < N and heights[rr][cc] >= heights[r][c] and not visited[rr][cc][src]:
                        visited[rr][cc][src] = 1
                        queue.append((rr, cc))
            
        
        for r in range(M):
            visited[r][0][0] = 1
            visited[r][N-1][1] = 1

            bfs(r, 0, 0)
            bfs(r, N-1, 1)
        
        for c in range(N):
            visited[0][c][0] = 1
            visited[M-1][c][1] = 1

            bfs(0, c, 0)
            bfs(M-1, c, 1)
        
        for r in range(M):
            for c in range(N):
                if visited[r][c][0] and visited[r][c][1]:
                    res.append([r, c])
        
        return res
 

C++代码：

 class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int H = heights.size();
        int W = heights[0].size();

        vector<vector<int>> res;

        vector<vector<bool>> pacific  = vector<vector<bool>>(H, vector<bool>(W, false));
        vector<vector<bool>> atlantic = vector<vector<bool>>(H, vector<bool>(W, false));

        for (int i=0; i<H; ++i) {
            bfs(heights, pacific, i, 0);
            bfs(heights, atlantic, i, W-1);
        }

        for (int j=0; j<W; ++j) {
            bfs(heights, pacific, 0, j);
            bfs(heights, atlantic, H-1, j);
        }

        for (int i=0; i<H; ++i) {
            for (int j=0; j<W; ++j) {
                if (pacific[i][j] && atlantic[i][j]) res.push_back({i, j});
            }
        }

        return res;
    }

private:
    int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};    

    void bfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
        if (visited[x][y]) return;

        visited[x][y] = true;

        queue<pair<int, int>> que;
        que.push({x, y});

        while(!que.empty()) {
            pair<int, int> cur = que.front(); que.pop();

            int curx = cur.first;
            int cury = cur.second;

            for (int i=0; i<4; ++i) {
                int xx = curx + dirs[i][0];
                int yy = cury + dirs[i][1];

                if (xx < 0 || xx >= heights.size() || yy < 0 || yy >= heights[0].size()) continue;
                if (heights[xx][yy] < heights[curx][cury] || visited[xx][yy]) continue;

                visited[xx][yy] = true;
                que.push({xx, yy});
            }
        }
    }
};
 

127. 单词接龙

字典wordList中从单词beginWord和endWord的转换序列是一个按下述规格形成的序列beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。
对于1 <= i <= k时，每个sᵢ都在wordList中。注意，beginWord不需要在wordList中。
sₖ == endWord。

给你两个单词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" 不在字典中，所以无法进行转换。
 

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord和wordList[i]由小写英文字母组成
beginWord != endWord
wordList中的所有字符串互不相同

Solution

本题的解法在于把每个单词当做图中的节点，如果两个单词之间只相差一个字母则为这一对节点添加一条边，这样题目就转换为从beginWord节点出发寻找到达endWord的一条最短路径。需要注意这种最短路径问题只能使用BFS而不能使用DFS进行求解，代码框架如下：

 visited = {word: 0 for word in wordList}
visited[beginWord] = 1
queue = deque([beginWord])

while queue:
    word = queue.popleft()

    if word == endWord:
        return visited[word]
    
    for newWord in adj(word):
        if not visited[newWord]:
            visited[newWord] = visited[word] + 1
            queue.append(newWord)
 

在编程时还有一些细节需要考虑：

如果在BFS之前先利用单词之间的差异进行建图容易出现超时的问题，因此更加合理的策略是在搜索相邻节点时再考虑单词之间的差异。
直接使用wordList进行查找的复杂度是O(n)，因此更高效的查找方式是先把wordList转换为set或者dict，这样查找的复杂度可以降到O(1)。

题目链接：

python代码：

 class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        from collections import deque

        wordSet = set(wordList)
        
        visited = {word: 0 for word in wordList}
        visited[beginWord] = 1
        queue = deque([beginWord])

        while queue:
            word = queue.popleft()

            if word == endWord:
                return visited[word]

            for i in range(len(word)):
                ww = list(word)
                for j in range(26):
                    ww[i] = chr(ord('a')+j)
                    newWord = "".join(ww)
                    
                    if newWord in wordSet and not visited[newWord]:
                        visited[newWord] = visited[word] + 1
                        queue.append(newWord)
        
        return 0
 

C++代码：

 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> visited;
        visited.insert(pair<string, int>(beginWord, 1));

        queue<string> que;
        que.push(beginWord);

        while (!que.empty()) {
            string word = que.front(); que.pop();
            int path = visited[word];

            for (int i=0; i<word.size(); ++i) {
                string newWord = word;
                
                if (newWord == endWord) return path;

                for (int j=0; j<26; ++j) {
                    newWord[i] = 'a' + j;

                    if (wordSet.find(newWord) != wordSet.end() && visited.find(newWord) == visited.end()) {
                        visited.insert(pair<string, int>(newWord, path+1));
                        que.push(newWord);
                    }
                }
            }
        }

        return 0;
    }
};
 

841. 钥匙和房间

给你一个数组rooms其中rooms[i]是你进入i号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回false。

示例1：

 输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
 

示例2：

 输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
 

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有rooms[i]的值互不相同

Solution

本题的BFS解法可以参考如下。

题目链接：

python代码：

 class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        N = len(rooms)

        from collections import deque

        queue = deque([0])
        visited = {i: 0 for i in range(N)}

        while queue:
            room = queue.popleft()
            visited[room] = 1

            for key in rooms[room]:
                if not visited[key]:
                    queue.append(key)
        
        for k, v in visited.items():
            if not v:
                return False
        
        return True
 

C++代码：

 class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int N = rooms.size();

        vector<bool> visited(N, false);
        visited[0] = true;

        // bfs
        queue<int> que;
        que.push(0);

        while (!que.empty()) {
            int key = que.front(); que.pop();

            for (int k: rooms[key]) {
                if (visited[k]) continue;

                visited[k] = true;
                que.push(k);
            }
        }

        for (int i=0; i<N; ++i) {
            if (!visited[i]) return false;
        }
        
        return true;
    }
};
 