一个成功的网站必须具备哪几个要素,企业网络营销论文,好的做问卷调查的网站好,WordPress推送服务文章目录1. 题目信息2. 解题2.1 DFS2.2 BFS1. 题目信息
给定一个由 ‘1’#xff08;陆地#xff09;和 ‘0’#xff08;水#xff09;组成的的二维网格#xff0c;计算岛屿的数量。一个岛被水包围#xff0c;并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你…
文章目录1. 题目信息2. 解题2.1 DFS2.2 BFS1. 题目信息
给定一个由 ‘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(vectorvectorchar 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(vectorvectorchar 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(i1 grid.size() grid[i1][j] 1)dfs(grid,i1,j);if(j1 grid[i].size() grid[i][j1] 1)dfs(grid,i,j1);}
};2.2 BFS
同样的采用BFS对点1的四周存在且为1的点入队迭代查找 竟然超时了有坑的代码请查看我的解题评论。 找到为1的点第一时间置0不要等到出队的时候再置0会造成其他周围的几个点没有及时置0造成的重复入队效率降低。
class Solution//BFS
{
public:int numIslands(vectorvectorchar grid){if(grid.empty())return 0;int i, j, r, c, numofislands 0;int x grid.size(), y grid[0].size();queuepairint,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(r1 x grid[r1][c] 1){q.push({r1,c});grid[r1][c] 0;}if(c1 y grid[r][c1] 1){q.push({r,c1});grid[r][c1] 0;}}}}}return numofislands;}
};
