德州哪里有做网站推广的,wordpress建小程序,自动采集的网站,如何注册公司需要多少资金给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外#xff0c;你可以假设该网格的四条边…给你一个由 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
思路一DFS
c解法
class Solution {
public:void dfs(vectorvectorchar grid,int i,int j,int m,int n){if(i0 || im || j0 || jn || grid[i][j] 0)return;grid[i][j] 0;dfs(grid,i 1,j,m,n);dfs(grid,i - 1,j,m,n);dfs(grid,i,j 1,m,n);dfs(grid,i,j - 1,m,n);}int numIslands(vectorvectorchar grid) {int m grid.size();int n grid[0].size();int num 0;for(int i0;im;i)for(int j0;jn;j){num grid[i][j] - 0;dfs(grid,i,j,m,n);}return num;}
};
分析
本题为岛屿类问题可用dfs的方式解决深度搜索将每个遍历过的格子赋值为2即标记为已遍历后面根据题目需要输出答案本题是将每个岛屿遍历一遍当到下一个未遍历的岛屿返回值加一
总结
本题考察对dfs的应用利用dfs每当遍历到一个未计数的岛屿则使用dfs将其设为已遍历的岛屿
