0934. Shortest Bridge ===================== 题目信息 -------- :题号: 0934 :难度: Medium :主题: 二进制矩阵、岛屿、最少翻转 :原题: `LeetCode 0934 `_ :重点: 输入恰好包含两个由上下左右相连的岛屿;只能把水格 ``0`` 改成陆地 ``1``,目标是用最少翻转使两岛连成一个岛 题目重述 -------- 给定 ``n x n`` 二进制矩阵 ``grid``。值为 ``1`` 的格子表示陆地,值为 ``0`` 的格子表示水;陆地只通过上、下、左、右四个方向连接。输入保证矩阵中恰好有两个彼此分离的岛屿。 一次操作可以选择一个水格并把它改为陆地。请返回至少需要翻转多少个水格,才能使原来的两个岛屿通过四方向陆地连通。 ``2 <= n <= 100``。 自建示例 -------- 只需填补两岛之间的一个水格: .. code-block:: text 输入:grid = [[1,0,0],[1,0,1],[0,0,1]] 输出:1 解释:把中间格 grid[1][1] 改为 1 后,左侧岛屿可以经该格连接到右侧岛屿。 两个岛位于对角远端: .. code-block:: text 输入:grid = [[1,0,0],[0,0,0],[0,0,1]] 输出:3 解释:两个陆地格的曼哈顿距离为 4,需要在它们之间填入三个水格才能形成四方向连续路径。