admin 管理员组文章数量: 887017
LeetCode 200.岛屿数量 C++
题目描述
给你一个由 '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'
来源：力扣（LeetCode）
链接：
解题思路1
bfs解法
1.首先特判，若数组为空，直接return 0。
2.数组非空的话，就bfs宽搜，搜一遍。
bfs函数：
1.首先row和column分别代表数组的行数和列数。
2.遍历数组中的每一个元素，如果是1的话，就入队并且置为0，计数器res++，对其进行bfs搜索。并且在bfs过程中，如果它相邻的点也是1的话，置0入队，注意此时res不用加，因为当前结点时与我们之前的结点相连接的，在该题目中属于同一个岛屿，继续搜，直至搜到相邻点没有1的情况，那么双重循环中的该元素bfs搜索完毕，双重for循环继续往下走，因为我们有置0的操作，所以访问过的结点不在被重复访问。
3.双重for循环结束，即对全部结点搜索结束。
4.返回计数器res。
代码1
class Solution {
public:void bfs(vector<vector<char>> &grid, int &res){int row=grid.size(); //行数int column=grid[0].size(); //列数queue<pair<int, int>> q; //存数据的队列，用pari<int,int>方便后面取当前行号与宽号for(int i=0;i<row;i++){ //遍历二维数组for(int j=0;j<column;j++){if(grid[i][j]=='1'){ //如果当前结点为11grid[i][j]='0'; //置0，表示后面不在访问res++; //结果+1q.push({i,j}); //入队while(!q.empty()){ auto p=q.front(); //用p记录队头元素q.pop(); //弹出int r=p.first; //当前元素的行号int c=p.second; //当前元素的列号if(r-1>=0&&grid[r-1][c]=='1'){ //当前上面的元素是否符合条件grid[r-1][c]='0'; //若符合，则置0q.push({r-1,c}); //入队}if(r+1<row&&grid[r+1][c]=='1'){ //同理，这是当前结点下面的元素的判断grid[r+1][c]='0';q.push({r+1,c});}if(c-1>=0&&grid[r][c-1]=='1'){ //同理，这是当前结点左面的元素的判断grid[r][c-1]='0';q.push({r,c-1});}if(c+1<column&&grid[r][c+1]=='1'){ //同理，这是当前结点右面的元素的判断grid[r][c+1]='0';q.push({r,c+1});}}}}}}int numIslands(vector<vector<char>>& grid) {int res=0; //计数器int row=grid.size(); //行数if(row==0){ //特判，空数组直接return 0return 0;}bfs(grid, res); //非空则bfs搜索一遍，结果保存在res中带回return res; //返回结果}
};
解题思路2
dfs解法
dfs函数的作用就是去扫描，在dfs的情况下扫到1，就置0，并且判断其相邻结点是否符合dfs要求。
主函数：
遍历二维数组，如果右元素等于1，就将结果res++，并且对其dfs扫一遍，dfs的作用是将其所有相邻的符合条件满足等于1的结点全部都置为0。
代码2
class Solution {
public:void dfs(vector<vector<char>> &grid,int i,int j){int row=grid.size(); //行数int col=grid[0].size(); //列数grid[i][j]='0'; //能进入dfs的都是符合条件的，所以将当前结点置0if(i-1>=0&&grid[i-1][j]=='1'){ 如果当前结点的上面的结点符合要求dfs(grid, i-1, j); //对当前结点上面的结点进行dfs搜索} if(i+1<=row-1&&grid[i+1][j]=='1'){ //同理这是当前结点的下面的结点的判断dfs(grid, i+1, j);}if(j-1>=0&&grid[i][j-1]=='1'){ //同理这是当前结点的左面的结点的判断dfs(grid, i, j-1);}if(j+1<=col-1&&grid[i][j+1]=='1'){ //同理这是当前结点的右面的结点的判断dfs(grid, i, j+1);}}int numIslands(vector<vector<char>>& grid) {int res=0; //计数器int row=grid.size(); //行数if(row==0){ //如果二维数组为空return res; //直接返回0}int col=grid[0].size(); //列数for(int i=0;i<row;i++){ //遍历二维数组for(int j=0;j<col;j++){if(grid[i][j]=='1'){ //如果当前结点为1res++; //计数器+1dfs(grid,i,j); //对当前结点dfs扫一遍，作用是把与其相邻的所有等于1的结点都置0}}}return res;}
};
本文标签： LeetCode 200岛屿数量 C
版权声明：本文标题：LeetCode 200.岛屿数量 C++ 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732352143h1533390.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论