在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

    现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

    返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

    示例 1：

    输入：A = [[0,1],[1,0]]
    输出：1
    示例 2：

    输入：A = [[0,1,0],[0,0,0],[0,0,1]]
    输出：2
    示例 3：

    输入：A = [[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

    提示：

    2 <= A.length == A[0].length <= 100
    A[i][j] == 0 或 A[i][j] == 1

    1. class Solution {
    2.     int[][] grid;
    3.     int n, m;
    4.     int[] dirs = new int[]{-1, 0, 1, 0, -1};
    5.     Deque<int[]> q = new LinkedList<>();
    6.     public int shortestBridge(int[][] grid) {
    7.         this.grid = grid;
    8.         n = grid.length; m = grid[0].length;
    9.         //dfs标记第一个块
    10.         for (int i = 0; i < n; ++i) {
    11.             boolean flag = false;
    12.             for (int j = 0; j < m; ++j) 
    13.                 if (grid[i][j] == 1) {
    14.                     grid[i][j] = -1;
    15.                     q.addLast(new int[]{i, j});
    16.                     dfs(i, j);
    17.                     flag = true;
    18.                     break;
    19.                 }
    20.             if (flag) break;
    21.         }
    22.         int res = -1;
    23.         //bfs寻找第二个块
    24.         while (!q.isEmpty()) {
    25.             int size = q.size();
    26.             res ++;
    27.             while (size -- > 0) {
    28.                 int[] t = q.pollFirst();
    29.                 int x = t[0], y = t[1];
    30.                 for (int i = 0; i < 4; ++i) {
    31.                     int a = x + dirs[i], b = y + dirs[i + 1];
    32.                     if (a < 0 || a >= n || b < 0 || b >= m) continue;
    33.                     if (grid[a][b] == -1) continue;
    34.                     //找到第二块陆地了
    35.                     if (grid[a][b] == 1) return res;
    36.                     grid[a][b] = -1;
    37.                     q.addLast(new int[]{a, b}); 
    38.                 }
    39.             }
    40.         }
    41.         return res;
    42.     }
    44.     void dfs(int x, int y) {
    45.         for (int i = 0; i < 4; ++i) {
    46.             int a = x + dirs[i], b = y + dirs[i + 1];
    47.             if (a < 0 || a >= n || b < 0 || b >= m) continue;
    48.             if (grid[a][b] == 0 || grid[a][b] == -1) continue;
    49.             q.addLast(new int[]{a, b});
    50.             grid[a][b] = -1;
    51.             dfs(a, b);
    52.         }
    53.     }
    54. }