给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：1
示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：
输入：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
提示：
n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] 为 0 或 1
grid 中恰有两个岛
- 通过dfs将所有旁边有0的1都放入队列中进行扩展，然后bfs搜索最短到达另外一个块的距离。
class Solution {
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int[] d = new int[]{1, 0, -1, 0, 1}; // 4个方向
int n;
public int shortestBridge(int[][] grid) {
n = grid.length;
for (int xi = 0; xi < n; xi++) {
for (int yi = 0; yi < n; yi++) {
if (grid[xi][yi] == 1) {
dfs(xi, yi, grid);
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int k = 0; k < size; k++) {
Pair<Integer, Integer> tem = q.poll();
int x = tem.getKey(), y = tem.getValue();
for (int j = 0; j < 4; j++) {
int fx = x + d[j];
int fy = y + d[j + 1];
if (fx >= 0 && fy >= 0 && fx < n && fy < n && grid[fx][fy] != -1) {
if (grid[fx][fy] == 1) return step;
grid[fx][fy] = -1;
q.add(new Pair(fx, fy));
}
}
}
step++;
}
}
}
}
return -1;
}
void dfs(int x, int y, int[][] grid) {
grid[x][y] = -1; //标记已访问
boolean ok = false; //判断是否右方向可以走
for (int i = 0; i < 4; i++) {
int fx = x + d[i];
int fy = y + d[i + 1];
if (fx >= 0 && fy >= 0 && fx < n && fy < n) {
if (grid[fx][fy] == 0) ok = true;
else if (grid[fx][fy] == 1) dfs(fx, fy, grid);
}
}
if (ok) q.add(new Pair(x, y)); //代表为边界节点
}
}