making-a-large-island

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change at most one <code>0</code> to be <code>1</code>.

Return the size of the largest island in <code>grid</code> after applying this operation.

An island is a 4-directionally connected group of <code>1</code>s.

&nbsp;
Example 1:

<pre>
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

Example 2:

<pre>
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

Example 3:

<pre>
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

largestIsland

Making A Large Island

Depth-First Search

Breadth-First Search

Union Find

Array

Matrix

给你一个大小为 <code>n x n</code> 二进制矩阵 <code>grid</code> 。最多 只能将一格&nbsp;<code>0</code> 变成&nbsp;<code>1</code> 。

返回执行此操作后，<code>grid</code> 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的&nbsp;<code>1</code> 形成。

&nbsp;

示例 1:

<pre>
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
</pre>

示例 2:

<pre>
输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。</pre>

示例 3:

<pre>
输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。</pre>

&nbsp;

提示：

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>
</ul>