【多源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.

题意：给定01网格中含有两个包含1的连通分量，求连接这两个连通分量的最短路径是多少

思路：把其中一个连通分量全部加到队列中，然后用 多源BFS求解

用dfs把其中一个连通分量全部加到队列中，并把1变成0（网格类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;
}
    }