# 0934. Shortest Bridge
###### tags: `Leetcode` `Medium` `FaceBook` `Microsoft` `DFS` `BFS`
Link: https://leetcode.com/problems/shortest-bridge/
## 思路
虽然想出来不难 但是不好写
之后可以再写一遍
**注意：遇到这种可以上下左右跑的题，可以单独写一个findneighbor function 来节省时间，另外在用比较复杂的数据结构 例如queue stack存点的时候可以存成i*columnNum+j来节省空间**

第二遍写的时候debug de了很久，就是因为在getComponents的时候是这样写的

while(!stack.isEmpty()){
    int node = stack.pop();
    int r = node/C;
    int c = node%C;
    colors[r][c] = t;
    for(int nei:neighbors(grid, r, c)){
        int nr = nei/C, nc = nei%C;
        if(grid[nr][nc]==1 && colors[nr][nc]==0){
            stack.push(nr*C+nc);
        }
    }
}

这样写的话一开始访问到一个没有被访问到的点会加进queue里面，之后再通过其他点访问到这个点还是会加进list，就导致了TLE
所以遇到这种**用visited检查的题，在找到邻居并判断出没有被visited之后，就改成visited**
## Code

class Solution {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> set = new HashSet<>();
    boolean[][] visited;
    
    public int shortestBridge(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        int[][] colors = getComponents(grid);
        
        for(int i = 0;i < colors.length;i++){
            for(int j = 0;j < colors[0].length;j++){
                if(colors[i][j]==1 && isEdge(grid,i,j)){
                    q.add(i*C+j);
                }
                if(colors[i][j]==2){
                    set.add(i*C+j);
                }
            }
        }
        
        int depth = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                int node = q.poll();
                if(set.contains(node)){
                    return depth-1;
                }
                for(int nei: neighbors(grid, node/C, node%C)){
                    int nr = nei/C, nc = nei%C;
                    if(colors[nr][nc]!=1){
                        q.add(nei);
                        colors[nr][nc]=1;
                    }
                }
            }
            depth++;
        }
        return -1;
        
    }
    public int[][] getComponents(int[][] grid){
        int R = grid.length, C = grid[0].length;
        int[][] colors = new int[R][C];
        int t = 0;
        
        for(int i = 0;i < R;i++){
            for(int j = 0;j < C;j++){
                if(colors[i][j]==0 && grid[i][j]==1){
                    Stack<Integer> stack = new Stack();
                    stack.push(i*C+j);
                    colors[i][j] = ++t;
                    
                    while(!stack.isEmpty()){
                        int node = stack.pop();
                        int r = node/C;
                        int c = node%C;
                        for(int nei:neighbors(grid, r, c)){
                            int nr = nei/C, nc = nei%C;
                            if(grid[nr][nc]==1 && colors[nr][nc]==0){
                                colors[nr][nc] = t;
                                stack.push(nr*C+nc);
                            }
                        }
                    }
                }
            }
        }
        return colors;
    }
    public List<Integer> neighbors(int[][] grid, int r, int c){
        int R = grid.length;
        int C = grid[0].length;
        List<Integer> ans = new ArrayList();
        if(r-1>=0) ans.add((r-1)*C+c);
        if(c-1>=0) ans.add(r*C+c-1);
        if(r+1<R) ans.add((r+1)*C+c);
        if(c+1<C) ans.add(r*C+c+1);
        return ans;
    }
    
    public boolean isEdge(int[][] grid, int x, int y){
        int R = grid.length;
        int C = grid[0].length;
        for(int nei:neighbors(grid,x,y)){
            if(grid[nei/C][nei%C]==0){
                return true;
            }
        }
        return false;
    }
}