0827. Making A Large Island

题目信息

题号:

0827

难度:

Hard

主题:

网格、岛屿连通、单格修改

原题:

LeetCode 0827

重点:

最多把一个 0 改成 1,岛屿只按四方向连接;相邻的同一岛屿只能计入一次,全为 1 时可不修改

题目重述

给定一个 n x n 二进制网格 grid。值为 1 的格子通过上、下、左、右相邻关系组成岛屿,岛屿面积等于其中格子数量。

可以选择至多一个值为 0 的格子并把它改为 1,也可以不做修改。请返回操作后能够得到的最大岛屿面积。若被修改格子的多个相邻方向连接到同一座原岛屿,该岛屿的面积只能计算一次;若网格原本全为 1,答案为 n * n。

1 <= n <= 500,网格元素只可能为 0 或 1。

自建示例

一次修改连接两座岛:

输入:grid = [[1,0,1],[1,0,0],[0,1,1]]
输出:5
解释:把中心格 (1,1) 改为 1,可连接左侧面积为 2 的岛和下方面积为 2 的岛,再加上新格自身,形成面积 5 的岛。

最小网格只有一个水格:

输入:grid = [[0]]
输出:1
解释:``n = 1`` 时唯一格子是水。把它改为 1 后得到一座面积为 1 的岛;这是能够取得的最大面积。