0934. Shortest Bridge

题目信息

题号:

0934

难度:

Medium

主题:

二进制矩阵、岛屿、最少翻转

原题:

LeetCode 0934

重点:

输入恰好包含两个由上下左右相连的岛屿;只能把水格 0 改成陆地 1,目标是用最少翻转使两岛连成一个岛

题目重述

给定 n x n 二进制矩阵 grid。值为 1 的格子表示陆地,值为 0 的格子表示水;陆地只通过上、下、左、右四个方向连接。输入保证矩阵中恰好有两个彼此分离的岛屿。

一次操作可以选择一个水格并把它改为陆地。请返回至少需要翻转多少个水格,才能使原来的两个岛屿通过四方向陆地连通。

2 <= n <= 100。

自建示例

只需填补两岛之间的一个水格:

输入:grid = [[1,0,0],[1,0,1],[0,0,1]]
输出:1
解释:把中间格 grid[1][1] 改为 1 后,左侧岛屿可以经该格连接到右侧岛屿。

两个岛位于对角远端:

输入:grid = [[1,0,0],[0,0,0],[0,0,1]]
输出:3
解释:两个陆地格的曼哈顿距离为 4,需要在它们之间填入三个水格才能形成四方向连续路径。