LeetCode 200. 岛屿数量（图的遍历）
LeetCode 200. 岛屿数量（图的遍历）
Michael阿明
发布于 2021-02-20 11:02:57
发布于 2021-02-20 11:02:57
1. 题目信息
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 DFS
图的连通性问题，主程序启动DFS，一次搜索中，遇到1的点将其置为0（只寻找1的点），后面不会再重复查找，对上下左右的点（如果存在且为1）递归查找。主程序中启动DFS的次数即为答案。
class Solution
{
public:
int numIslands(vector<vector<char>>& grid)
{
int i, j, numofislands = 0;
for(i = 0; i < grid.size(); ++i)
{
for(j = 0; j < grid[i].size(); ++j)
{
if(grid[i][j] == '1')
{
numofislands++;
dfs(grid,i,j);
}
}
}
return numofislands;
}
void dfs(vector<vector<char>>& grid, int i, int j)
{
grid[i][j] = '0';//标记走过了，修改了地图（不影响解题）
if(i-1 >= 0 && 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(i+1 < grid.size() && grid[i+1][j] == '1')
dfs(grid,i+1,j);
if(j+1 < grid[i].size() && grid[i][j+1] == '1')
dfs(grid,i,j+1);
}
};2.2 BFS
同样的采用BFS，对点1的四周存在且为1的点入队，迭代查找 竟然超时了，有坑的代码请查看我的解题评论。
找到为1的点，第一时间置0，不要等到出队的时候再置0，会造成其他周围的几个点没有及时置0，造成的重复入队，效率降低。
class Solution//BFS
{
public:
int numIslands(vector<vector<char>>& grid)
{
if(grid.empty())
return 0;
int i, j, r, c, numofislands = 0;
int x = grid.size(), y = grid[0].size();
queue<pair<int,int> > q;
for(i = 0; i < x; ++i)
{
for(j = 0; j < y; ++j)
{
if(grid[i][j] == '1')
{
numofislands++;
q.push({i,j});
while(!q.empty())
{
r = q.front().first;
c = q.front().second;
//grid[r][c] = '0';//标记走过了(不要写在这里，否则，会重复检查很多遍)
q.pop();
if(r-1 >= 0 && grid[r-1][c] == '1')
{
q.push({r-1,c});
grid[r-1][c] = '0';//写在这里，找到了就马上第一时间标记
}
if(c-1 >= 0 && grid[r][c-1] == '1')
{
q.push({r,c-1});
grid[r][c-1] = '0';
}
if(r+1 < x && grid[r+1][c] == '1')
{
q.push({r+1,c});
grid[r+1][c] = '0';
}
if(c+1 < y && grid[r][c+1] == '1')
{
q.push({r,c+1});
grid[r][c+1] = '0';
}
}
}
}
}
return numofislands;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
