shortest-bridge

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> where <code>1</code> represents land and <code>0</code> represents water.

An island is a 4-directionally connected group of <code>1</code>&#39;s not connected to any other <code>1</code>&#39;s. There are exactly two islands in <code>grid</code>.

You may change <code>0</code>&#39;s to <code>1</code>&#39;s to connect the two islands to form one island.

Return the smallest number of <code>0</code>&#39;s you must flip to connect the two islands.

&nbsp;
Example 1:

<pre>
Input: grid = [[0,1],[1,0]]
Output: 1
</pre>

Example 2:

<pre>
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
</pre>

Example 3:

<pre>
Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li>There are exactly two islands in <code>grid</code>.</li>
</ul>

shortestBridge

Shortest Bridge

Minimum Number of Operations to Make X and Y Equal

minimum-number-of-operations-to-make-x-and-y-equal

使 X 和 Y 相等的最少操作次数

Depth-First Search

Breadth-First Search

Array

Matrix

给你一个大小为 <code>n x n</code> 的二元矩阵 <code>grid</code> ，其中 <code>1</code> 表示陆地，<code>0</code> 表示水域。

岛 是由四面相连的 <code>1</code> 形成的一个最大组，即不会与非组内的任何其他 <code>1</code> 相连。<code>grid</code> 中 恰好存在两座岛 。

<div class="original__bRMd">
<div>
你可以将任意数量的 <code>0</code> 变为 <code>1</code> ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 <code>0</code> 的最小数目。
</div>
</div>

&nbsp;

示例 1：

<pre>
输入：grid = [[0,1],[1,0]]
输出：1
</pre>

示例 2：

<pre>
输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
</pre>

示例 3：

<pre>
输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>
	<li><code>grid</code> 中恰有两个岛</li>
</ul>