LeetCode刷题笔记优先搜索网格结构深度优先搜索

编程入门行业动态更新时间:2024-10-20 03:27:19

网格结构深度优先搜索简介

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。

二维数组深度优先搜索的一般写法：

一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否满足开始搜索的条件，如果可以即在辅函数中进行搜索。

辅函数负责实现深度优先搜索过程。这一过程可以使用递归调用调用实现；当然，我们也可以使用栈（stack）实现深度优先搜索，与使用队列（queue）实现广度优先搜索类比。但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时推荐使用递归式写法，可以将深度优先搜索与回溯算法进行类比。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。

在辅函数里，一个一定要注意的点是辅函数内递归搜索时，对矩阵边界条件的判定。边界判定一般有两种写法：一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合法（即判断放在辅函数第一行）。两种方法任选一种符合自身代码习惯的写法即可。

二维数组四向遍历小技巧：对于四个方向的遍历，可以创造一个数组 direction = [-1, 0, 1, 0, -1]，每相邻两位即为上下左右四个方向之一，即：

左移 x+=direction[0]; y+=direction[1]；上移 x+=direction[1]; y+=direction[2]；右移 x+=direction[2]; y+=direction[3]；下移 x+=direction[3]; y+=direction[4]；

695 岛屿的最大面积

给定一个大小为 m x n 的二维 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 。

解析：

本题是十分标准的搜索题，我们编写主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否满足开始搜索的条件，如果可以即在辅函数中进行搜索。

主函数寻找符合启动辅助函数进行搜索的位置，并记录辅助函数计算的岛屿最大值。我们可以使用双重循环实现，双重循环遍历矩阵的每一个位置，当发现岛屿即位置值为1时，开始用辅助函数搜索。

辅函数中从开始搜索的位置向相邻四个方向递归搜索值为1的位置，并累计岛屿面积。搜索过程中我们对边界条件的判定采用先判断再搜索的方式，即先判断搜索节点是否越界，再决定是否继续进行深度递归搜索。遍历值为1的节点之后注意要将其值置为0，避免重复遍历无限递归。

class Solution {// 四个方向的遍历vector<int> direction = {-1,0,1,0,-1};
public:int dfs(vector<vector<int>>& grid, int i, int j){if(grid[i][j] == 0) return 0;// 遍历后值置为 0grid[i][j] = 0;// 四向深度优先搜索int x, y, area = 1;for(int s=0;s<4;++s){x = i+direction[s];y = j+direction[s+1];if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()){area += dfs(grid,x,y);}}return area;}int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.empty() || grid[0].empty()){return 0;}int maxArea = 0;// 寻找符合启动辅助函数进行搜索的位置for(int i=0;i<grid.size();++i){for(int j=0;j<grid[0].size();++j){if(grid[i][j] == 1){maxArea = max(maxArea,dfs(grid,i,j));}}}return maxArea;}
};

200 岛屿数量

给定一个大小为 m x n 的二维 0-1 矩阵 grid ，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛
屿，每个格子只与其上下左右四个格子相邻。求二维数组中一共有多少个岛屿。

输入一个二维数组，输出是一个整数，表示岛屿数量。

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出：3

解析：

本题与695 岛屿的最大面积题十分相似，我们同样编写主函数和辅函数：

主函数寻找符合启动辅助函数进行搜索的位置，每找到这样一个位置就相当与找到一个岛屿。使用双重循环遍历矩阵的每一个位置，当发现岛屿即位置值为1时，开始用辅助函数搜索。

辅函数中从开始搜索的位置向相邻四个方向递归搜索，将属于同一岛屿的网格从'1' 置为'0'，避免重复计算岛屿数量。同样搜索过程中我们需要对边界条件进行判定，仍采用先判断是否越界，再进行递归搜索的方式。

class Solution {vector<int> direction={-1,0,1,0,-1};
public:void dfs(vector<vector<char>>& grid, int i, int j){if(grid[i][j] == '0') return;grid[i][j] = '0';int x, y;for(int s=0;s<4;++s){x = i+direction[s];y = j+direction[s+1];if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()){dfs(grid,x,y);}}}int numIslands(vector<vector<char>>& grid) {if(grid.empty() || grid[0].empty()){return 0;}int ans = 0;for(int i=0;i<grid.size();++i){for(int j=0;j<grid[0].size();++j){if(grid[i][j] == '1'){dfs(grid,i,j);++ans;}}}return ans;}
};

463 岛屿的周长

给定一个大小为 m x n 的二维 0-1 矩阵 grid ，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛
屿，每个格子只与其上下左右四个格子相邻。求二维数组中一个或多个岛屿的周长。

输入一个二维数组，输出是一个整数，表示岛屿的周长。

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

解析：

本题与695 岛屿的最大面积题十分相似，我们同样编写主函数和辅函数：

主函数寻找符合启动辅助函数进行搜索的位置，并记录辅助函数计算的每个岛屿的周长。使用双重循环遍历矩阵的每一个位置，当发现岛屿即位置值为1时，开始用辅助函数搜索。

辅函数中从开始搜索的位置向相邻四个方向递归搜索。对于一个值为1的位置的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。因此，我们可以遍历每个陆地格子，看其四个方向是否为边界或者水域：如果是，则将这条边作为岛屿的周长的一段加入中结果；如果不是，则不加入周长并继续递归搜索。

搜索过程中我们对边界条件的判定采用先判断再搜索的方式，即先判断搜索节点是否越界，再决定是否继续进行深度递归搜索。遍历值为1的节点之后注意要将其值置为2，避免重复遍历无限递归和错误地周长计算。

class Solution {vector<int> direction={-1,0,1,0,-1};
public:int dfs(vector<vector<int>>& grid, int i, int j){if(grid[i][j]==0) return 1;if(grid[i][j]==2) return 0;grid[i][j] = 2;int x, y, perimeter = 0;for(int s=0;s<4;++s){int x = i+direction[s];int y = j+direction[s+1];if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()){perimeter += dfs(grid,x,y);}else{++perimeter;}}return perimeter;}int islandPerimeter(vector<vector<int>>& grid) {if(grid.empty() || grid[0].empty()){return 0;}int ans = 0;for(int i=0;i<grid.size();++i){for(int j=0;j<grid[0].size();++j){if(grid[i][j]==1){ans += dfs(grid,i,j);}}}return ans;}
};

417 太平洋大西洋水流问题

给定一个二维的非负整数矩阵，每个位置的值表示海拔高度。假设左边和上边是太平洋，右边和下边是大西洋，求从哪些位置向下流水，可以流到太平洋和大西洋。水只能从海拔高的位置流到海拔低或相同的位置。

输入是一个二维的非负整数数组，表示海拔高度。输出是一个二维的数组，其中第二个维度大小固定为 2，表示满足条件的位置坐标。

输入如下的 5x5 矩阵:太平洋 ~   ~   ~   ~   ~ ~  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]] (上图中带括号的位置).

解析：

虽然题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那么在不剪枝的情况下复杂度会很高。因此我们可以反过来想，从两个大洋开始向上流，这样我们只需要对矩形四条边进行搜索。搜索完成后，只需遍历一遍矩阵，满足条件的位置即为两个大洋向上流都能到达的位置。

具体来说，我们仍然使用主函数加辅函数的形式：

主函数用于从边界（即大洋位置）开始搜索满足数值上升的路径（即可以留到大洋的位置）。结合辅函数完成搜索之后，遍历矩阵中所有的位置，找到既能流到太平洋又可以流到大西洋的位置。

辅函数中使用递归实现当前位置的四向搜索，继续递归的边界条件是下一位置在矩阵内且该位置的值大于等于当前值。搜索过程中将已访问的位置标记，避免重复搜索。

class Solution {vector<int> direction={-1,0,1,0,-1};
public:void dfs(vector<vector<int>>& heights, vector<vector<bool>>& can_reach, int i, int j){if(can_reach[i][j]) return;can_reach[i][j] = true;int x, y;for(int s=0;s<4;++s){x = i+direction[s];y = j+direction[s+1];if(x>=0 && x<heights.size() && y>=0 && y<heights[0].size() && heights[i][j]<=heights[x][y]){dfs(heights,can_reach,x,y);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {if(heights.empty() || heights[0].empty()){return {};}int m = heights.size(), n = heights[0].size();vector<vector<int>> ans;// 从边界四向搜索上升路径vector<vector<bool>> can_reach_p(m,vector<bool>(n,false));vector<vector<bool>> can_reach_a(m,vector<bool>(n,false));for(int i=0;i<m;++i){dfs(heights,can_reach_p,i,0);dfs(heights,can_reach_a,i,n-1);}for(int i=0;i<n;++i){dfs(heights,can_reach_p,0,i);dfs(heights,can_reach_a,m-1,i);}// 标记 can_reach_p 和 can_reach_a 搜索均为 true 即可以流向太平洋也可以流向大西洋的节点for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(can_reach_p[i][j] && can_reach_a[i][j]){ans.push_back({i,j});}}}return ans;}
};

130 被围绕的区域

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

输入一个二维数组，输出是一个被围绕区域覆盖之后的二维数组。

输入：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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解析：

本题和417 太平洋大西洋水流问题思路相似，虽然题目是要求找到所有被 'X' 围绕的区域，我们可以反向考虑找到所有没有被围绕的区域，即与边界连接的区域，然后将剩余的区域全部用'X' 覆盖。

所以本题我们也从边界开始搜索，主函数完成两个任务：首先从矩阵的四个边界搜索没有被围绕的区域，开始搜索的条件是发现边界位置值为'O'字符；然后调用辅函数遍历矩阵将所有被围绕的区域用'X' 覆盖。辅函数完成当前位置的四向遍历，递归搜索出没有被围绕的区域，为了区分没有被围绕的区域和被围绕区域，我们使用'Y'字符标识没有被围绕的区域。

完成深度优先搜索之后，矩阵中包含三种字符覆盖字符'X' ，没有被围绕的区域'Y'，被围绕区域'O'，遍历矩阵将所有'Y'字符用'O'字符覆盖，将所有'O'字符用'X'字符覆盖，就解决了本题。

class Solution {vector<int> direction={-1,0,1,0,-1};
public:void dfs(vector<vector<char>>& board, int i, int j){if(board[i][j] == 'Y') return;// 将没有被围绕的区域用 'Y' 字符标识board[i][j] = 'Y';int x,y;for(int s=0;s<4;++s){x = i+direction[s];y = j+direction[s+1];if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && board[x][y]=='O'){dfs(board,x,y);}}}void solve(vector<vector<char>>& board) {if(board.empty() || board[0].empty()){return;}int m = board.size(), 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);}}// 将所有'Y'字符用'O'字符覆盖，将所有'O'字符用'X'字符覆盖for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(board[i][j]=='Y'){board[i][j]='O';}else if(board[i][j]=='O'){board[i][j]='X';}}}}
};