普拓网站建设,济南行业网站建设,wordpress 连接qq视频教程,保定百度网站建设1020.飞地的数量
分析#xff1a;求不跟边界接壤的陆地的数量
思路一#xff1a;深度优先遍历
先从四个侧边找陆地#xff0c;然后进行深度优先遍历#xff0c;把所有接壤的陆地#xff08;1#xff09;全部转换成海洋#xff08;0#xff09; 深度优先遍历#xf…1020.飞地的数量
分析求不跟边界接壤的陆地的数量
思路一深度优先遍历
先从四个侧边找陆地然后进行深度优先遍历把所有接壤的陆地1全部转换成海洋0 深度优先遍历从四个方向进行递归遍历遍历整个图统计所有陆地的数量。
class Solution {
public:int direct[4][2]{{0,1},{0,-1},{1,0},{-1,0}};int res0;void dfs(vectorvectorintgrid,int x,int y){grid[x][y]0;for(int i0;i4;i){int nextxxdirect[i][0];int nextyydirect[i][1];if(nextx0 nextxgrid.size() nexty0 nextygrid[0].size()){//边界条件if(grid[nextx][nexty]1){grid[nextx][nexty]0;dfs(grid,nextx,nexty);}}}}int numEnclaves(vectorvectorint grid) {int ngrid.size(),mgrid[0].size();for(int i0;in;i){if(grid[i][0]1) dfs(grid,i,0);//左侧边if(grid[i][m-1]1) dfs(grid,i,m-1);//右侧边}for(int j0;jm;j){if(grid[0][j]1) dfs(grid,0,j);//上侧边if(grid[n-1][j]1) dfs(grid,n-1,j);//下侧边}for(int i1;in-1;i){//遍历整个图for(int j1;jm-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 res0;void dfs(vectorvectorcharboard,char target,int x,int y){board[x][y]target;res;for(int i0;i4;i){int nextxxdirect[i][0];int nextyydirect[i][1];if(nextx0 nextxboard.size() nexty0 nextyboard[0].size()){if(board[nextx][nexty]O){board[nextx][nexty]target;dfs(board,target,nextx,nexty);}}}}void solve(vectorvectorchar board) {int nboard.size(),mboard[0].size();for(int i0;in;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 j0;jm;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 i0;in;i){for(int j0;jm;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(vectorvectorintheights,vectorvectorboolvisted,int x,int y){if(visted[x][y]) return;visted[x][y]true;for(int i0;i4;i){int nextxxdirect[i][0];int nextyydirect[i][1];if(nextx0 nextxheights.size() nexty0 nextyheights[0].size()){if(heights[x][y]heights[nextx][nexty])//本来是从高到低这是倒着推所以低到高dfs(heights,visted,nextx,nexty);}}}vectorvectorint pacificAtlantic(vectorvectorint heights) {int nheights.size(),mheights[0].size();vectorvectorintres;vectorvectorboolpacific(n,vectorbool(m,false));//太平洋vectorvectorboolatlantic(n,vectorbool(m,false));//大西洋for(int i0;in;i){dfs(heights,pacific,i,0);//从左侧太平洋出发dfs(heights,atlantic,i,m-1);//从右侧大西洋出发}for(int j0;jm;j){dfs(heights,pacific,0,j);//从上侧太平洋出发dfs(heights,atlantic,n-1,j);//从下侧大西洋出发}for(int i0;in;i){for(int j0;jm;j){if(pacific[i][j] atlantic[i][j])//从大西洋和太平洋都可以流过res.push_back({i,j});}}return res;}
};
