玉溪市网站建设_网站建设公司_前端工程师_seo优化

一、题目描述

二、算法原理

思路：基于下面这个链接的题目，统计遍历过程中所有的岛屿个数就行

https://blog.csdn.net/2403_84958571/article/details/157102889?spm=1011.2415.3001.10575&sharefrom=mp_manage_link

三、代码实现

class Solution { vector<vector<bool>> tmp; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int maxi; typedef pair<int,int> PII; public: int maxAreaOfIsland(vector<vector<int>>& grid) { tmp.resize(grid.size(),vector<bool>(grid[0].size(),false)); maxi = 0;//岛屿的面积 for(int i = 0; i < grid.size(); i ++) { for(int k = 0; k <grid[0].size(); k++) { if(grid[i][k] == 1 && tmp[i][k] == false) { Checkgrid(grid,i,k);//找到岛屿入口 } } } return maxi; } void Checkgrid(vector<vector<int>>& grid,int i,int k) { queue<PII> que;//使用层序遍历，查找相连的岛屿 que.push({i,k}); int count = 1;//同意岛屿个数 tmp[i][k] = true; while(que.size()) { auto [x,y] = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int a = x + dx[i]; int b = y + dy[i]; if(a >= 0 && a < grid.size() && b >= 0 && b < grid[0].size() && grid[a][b] == 1 && tmp[a][b] == false) { que.push({a,b}); count++; tmp[a][b] = true; } } } maxi = max(maxi,count); } };