在給定的二維二進制數組 A 中，存在兩座島。（島是由四面相連的 1 形成的一個最大組。）

現在，我們可以將 0 變為 1，以使兩座島連接起來，變成一座島。

返回必須翻轉的 0 的最小數目。（可以保證答案至少是 1。）

示例 1：

輸入：[[0,1],[1,0]]
輸出：1

代碼

class Solution {public void  helper(int[][] A,int[][] dir) {//dfs找出第一座島，標為2for(int i=0;i<A.length;i++)for(int j=0;j<A[0].length;j++)if(A[i][j]==1){dfs(A,dir,i,j);return;}}Queue<int[]> queue=new LinkedList<>();public int shortestBridge(int[][] A) {int[][] dir=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};int n=A.length,m=A[0].length;helper(A,dir);while (!queue.isEmpty())//bfs{int[] e=queue.poll();int ex=e[0],ey=e[1],el=e[2];for(int[] d:dir)//向4個方向蔓延{int nextX=ex+d[0],nextY=ey+d[1];if(nextX<0||nextX>=A.length||nextY<0||nextY>=A[0].length||A[nextX][nextY]==2)continue;//不能走的點if(A[nextX][nextY]==1) return el;queue.offer(new int[]{nextX,nextY,el+1});A[nextX][nextY]=2;//標記為第一座島嶼，避免重復訪問}}return -1;}public void dfs(int[][] A,int[][] dir,int x,int y) {A[x][y]=2;queue.offer(new int[]{x,y,0});for(int[] d:dir){int nextX=x+d[0],nextY=y+d[1];if(nextX<0||nextX>=A.length||nextY<0||nextY>=A[0].length||A[nextX][nextY]!=1)continue;dfs(A, dir, nextX, nextY);}}
}