day-63 代码随想录算法训练营（19） 图论 part 02

1020.飞地的数量

分析：求不跟边界接壤的陆地的数量

思路一：深度优先遍历

• 先从四个侧边找陆地，然后进行深度优先遍历，把所有接壤的陆地（1）全部转换成海洋（0）
  • 深度优先遍历：从四个方向进行递归遍历
• 遍历整个图，统计所有陆地的数量。

class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<int>>&grid,int x,int y){grid[x][y]=0;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<grid.size() && nexty>=0 && nexty<grid[0].size()){//边界条件if(grid[nextx][nexty]==1){grid[nextx][nexty]=0;dfs(grid,nextx,nexty);}}}}int numEnclaves(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(grid,i,0);//左侧边if(grid[i][m-1]==1) dfs(grid,i,m-1);//右侧边}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs(grid,0,j);//上侧边if(grid[n-1][j]==1) dfs(grid,n-1,j);//下侧边}for(int i=1;i<n-1;i++){//遍历整个图for(int j=1;j<m-1;j++){if(grid[i][j]==1) res++;}}return res;}
};

130.被围绕的区域

思路一：dfs

• 依然是从四个侧面把陆地深度优先遍历，然后改成 A 字符
• 然后遍历整个图，把剩余的陆地（必然被海水包裹）变为海水，A 字符变为陆地

class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<char>>&board,char target,int x,int y){board[x][y]=target;res++;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<board.size() && nexty>=0 && nexty<board[0].size()){if(board[nextx][nexty]=='O'){board[nextx][nexty]=target;dfs(board,target,nextx,nexty);}}}}void solve(vector<vector<char>>& board) {int n=board.size(),m=board[0].size();for(int i=0;i<n;i++){if(board[i][0]=='O') dfs(board,'A',i,0);//左侧边if(board[i][m-1]=='O') dfs(board,'A',i,m-1);//右侧边}for(int j=0;j<m;j++){if(board[0][j]=='O') dfs(board,'A',0,j);//上侧边if(board[n-1][j]=='O') dfs(board,'A',n-1,j);//下侧边}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='A') board[i][j]='O';//所有的A变为Oelse if(board[i][j]=='O') board[i][j]='X';//所有的O变为X}} }
};

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

思路一：深度优先遍历

• 分别从大西洋和太平洋一侧，倒着推得到两个数组
• 当两个数组都经过同一位置时，说明可以流向两边

class Solution {
public:int direct[4][2]={{1,0},{-1,0},{0,1},{0,-1}};void dfs(vector<vector<int>>&heights,vector<vector<bool>>&visted,int x,int y){if(visted[x][y]) return;visted[x][y]=true;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<heights.size() && nexty>=0 && nexty<heights[0].size()){if(heights[x][y]<=heights[nextx][nexty])//本来是从高到低，这是倒着推，所以低到高dfs(heights,visted,nextx,nexty);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {int n=heights.size(),m=heights[0].size();vector<vector<int>>res;vector<vector<bool>>pacific(n,vector<bool>(m,false));//太平洋vector<vector<bool>>atlantic(n,vector<bool>(m,false));//大西洋for(int i=0;i<n;i++){dfs(heights,pacific,i,0);//从左侧太平洋出发dfs(heights,atlantic,i,m-1);//从右侧大西洋出发}for(int j=0;j<m;j++){dfs(heights,pacific,0,j);//从上侧太平洋出发dfs(heights,atlantic,n-1,j);//从下侧大西洋出发}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(pacific[i][j] && atlantic[i][j])//从大西洋和太平洋都可以流过res.push_back({i,j});}}return res;}
};