[multi source BFS] 934 Shortest Bridge

934. Shortest Bridge

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

The question ： Given 01 The grid contains two contains 1 The connected component of , Find the shortest path connecting the two connected components

Ideas ： Add one of the connected components to the queue , And then use   Multi-source BFS solve

use dfs Add one of the connected components to the queue , And put 1 become 0（ Grid class dfs）

class Solution {

final int INF=0X3f3f3f3f;
int[] dx={-1,0,1,0},dy={0,1,0,-1};
int[][] g,d;
Queue<Node>q=new LinkedList<>();
class Node{
    int x,y;
    public Node(){}
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}

public int shortestBridge(int[][] grid){
    g=grid;
    d=new int[g.length][g[0].length];
    for(int i=0;i<d.length;i++){
        Arrays.fill(d[i],0x3f3f3f3f);
    }
    for(int i=0;i<g.length;i++){
        for(int j=0;j<g[0].length;j++){
            if(g[i][j]==1){
                dfs(i,j);
                return bfs();
            }
        }
    }
    return -1;
}
void dfs(int x,int y){
    g[x][y]=2;
    d[x][y]=0;
    q.add(new Node(x,y));
    for(int i=0;i<4;i++){
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<0||a>=g.length||b<0||b>=g[0].length||g[a][b]!=1){
            continue;
        }
        dfs(a,b);
    }
}
int bfs(){
    while(!q.isEmpty()){
        Node t=q.poll();
        for(int i=0;i<4;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(x<0||x>=g.length||y<0||y>=g[0].length||d[x][y]<=d[t.x][t.y]+1)
            continue;
            d[x][y]=d[t.x][t.y]+1;
            if(g[x][y]==1)return d[x][y]-1;
            q.add(new Node(x,y));
        }
    }
    return -1;
}
    }