您的位置:首页 > 健康 > 美食 > 武汉市工程建设信息网_工业互联网平台首先要提高数据的挖掘能力_logo设计_怎么在百度上推广

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

2024/10/31 6:48:57 来源:https://blog.csdn.net/weixin_65043441/article/details/142986018  浏览:    关键词:武汉市工程建设信息网_工业互联网平台首先要提高数据的挖掘能力_logo设计_怎么在百度上推广
武汉市工程建设信息网_工业互联网平台首先要提高数据的挖掘能力_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;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com