LeetCode 200. 岛屿数量（图的遍历）

文章目录

• • 1. 题目信息
  • 2. 解题
  • • 2.1 DFS
    • 2.2 BFS

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;} }; 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的LeetCode 200. 岛屿数量（图的遍历）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。