200. 岛屿数量 - 力扣LeetCode200. 岛屿数量 - 给你一个由 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 或 1https://leetcode.cn/problems/number-of-islands/题目描述给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。 岛屿总是被水包围并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。 此外你可以假设该网格的四条边均被水包围。考点二维网格 BFS/DFS、连通块计数、标记访问思路分析核心思想连通块统计遍历整个网格只要遇到未访问过的陆地1就代表找到一座新岛屿岛屿计数 1 再用 BFS 把这块岛屿相连的所有陆地全部标记为已访问避免重复统计。BFS 作用从当前陆地出发向上下左右 4 个方向扩散把同岛屿所有陆地打标记。方向数组dx/dy简化 4 个方向的遍历是网格类题标准写法。vis 数组记录该坐标是否已经被遍历过防止重复入队、重复计数。class Solution { int dx[4]{0,0,1,-1}; int dy[4]{1,-1,0,0}; bool vis[301][301]; int m,n; public: int numIslands(vectorvectorchar grid) { mgrid.size(),ngrid[0].size(); int ret0; for(int i0;im;i) { for(int j0;jn;j) { if(grid[i][j]1!vis[i][j]) { ret; bfs(grid,i,j); } } } return ret; } void bfs(vectorvectorchar grid,int i,int j) { queuepairint ,intq; q.push({i,j}); vis[i][j]true; while(q.size()) { auto [a,b]q.front(); q.pop(); for(int k0;k4;k) { int xadx[k]; int ybdy[k]; if(x0xmy0yngrid[x][y]1!vis[x][y]) { q.push({x,y}); vis[x][y]true; } } } } };
