武汉市工程建设信息网_工业互联网平台首先要提高数据的挖掘能力_logo设计_怎么在百度上推广

题目描述：

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是11，因为岛屿只能包含水平或垂直这四个方向上的1。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 为 0 或 1

题目链接：

. - 力扣（LeetCode）

解题主要思路：

这题同样是 “渲染图像” 升级而来的，跟 “岛屿数量” 那道题基本没差别，会 “岛屿数量” 那道题就肯定会这题。一块岛屿无非就是调用一次 "图像渲染"，但是比如说有三块岛屿，我找出一块后，如何让这块岛屿不影响另外两块岛屿的搜索呢？很简单，两种方式，一种是当我们找出‘陆地’后，将其改成‘海洋’；另一种方式就是定义一个数组vis，用来记录该元素是否已经被搜索过了，这样的好处就是不会更改原数据。这次我采用第一种解题方式，“岛屿数量” 这道题我提供了两种解法，可以点击下方的链接学习学习。
岛屿数量链接：https://blog.csdn.net/weixin_65043441/article/details/142984279

解题代码：

class Solution {
public:typedef pair<int, int> PII;int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;int maxAreaOfIsland(vector<vector<int>>& grid) {int ret = 0;m = grid.size(), n = grid[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j]) ret = max(ret, bfs(grid, i, j));}}return ret;}int bfs(vector<vector<int>>& grid, int r, int c){int ret = 1;queue<PII> que;que.push(make_pair(r, c));grid[r][c] = 0;  // 消除影响while (que.size()) {auto [a, b] = que.front();que.pop();for (int i = 0; i < 4; ++i) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {++ret;que.push(make_pair(x, y));grid[x][y] = 0;  // 消除影响}}}return ret;}
};