200岛屿数量

题目给你一个由 ‘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思路这题典型的bfs或者dfs。bfs解题思路就是先按照顺序寻找岛屿的一部分然后向四周发散直到碰到水标记出完整的岛屿并计数然后重复这一步直到遍历完整个表格。代码class Solution{public: int numIslands(vectorvectorchargrid){introwgrid.size();if(!row)return0;intres0;intcolgrid[0].size();vectorvectorboolvisit(row,vectorbool(col,false));for(intr0;rrow;r){for(intc0;ccol;c){if((grid[r][c]-01)!visit[r][c]){ bfs(grid,visit,r,c);res;} } } return res;} void bfs(vectorvectorchargrid,vectorvectorboolvisit,int row,int col){ queuepairint,intq;q.push({row,col});visit[row][col]true;while(!q.empty()){pairint,inttempq.front();q.pop();vectorvectorintdis{{0,-1},{0,1},{1,0},{-1,0}};for(inti0;idis.size();i){intrtemp.firstdis[i][0];intctemp.seconddis[i][1];if(r0rgrid.size()c0cgrid[0].size()(grid[r][c]-0)1!visit[r][c]){q.push({r,c});visit[r][c]true;}}}}};时间复杂度o(n)o(n)o(n)空间复杂度o(n)o(n)o(n)注意这道题代码量比较大需要注意细节此外题目中表示岛屿的1是char格式的感谢 华南溜达虎 力扣 blind75 指导