0934. Shortest Bridge¶
题目信息¶
- 题号:
0934
- 难度:
Medium
- 主题:
二进制矩阵、岛屿、最少翻转
- 原题:
- 重点:
输入恰好包含两个由上下左右相连的岛屿;只能把水格
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,需要在它们之间填入三个水格才能形成四方向连续路径。