0934 Shortest Bridge

0934 Shortest Bridge.java

class Solution {
    private int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    private int r = 0, c = 0;
    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] visited;

    private void dfs(int[][] A, int i, int j) {
        A[i][j] = 2;
        for (int[] dir : dirs) {
            int ni = i + dir[0];
            int nj = j + dir[1];
            if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
                if (A[ni][nj] == 1)
                    dfs(A, ni, nj);
                if (A[ni][nj] == 0 && !visited[i][j]) {
                    q.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
    }

    public void set_l1(int[][] A) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (A[i][j] == 1) {
                    dfs(A, i, j);
                    return;
                }
            }
        }
    }
    
    public int shortestBridge(int[][] A) {
        r = A.length;
        c = A[0].length;
        visited = new boolean[r][c];        
        set_l1(A);        
        int step = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            
            for (int cnt = 0; cnt < size; cnt++) {
                int[] curr = q.poll();
                int i = curr[0];
                int j = curr[1];
                
                for (int[] dir : dirs) {
                    int ni = i + dir[0];
                    int nj = j + dir[1];
                    
                    if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
                        if (A[ni][nj] == 1) {
                            return step;
                        }
                        else if (A[ni][nj] == 0) {
                            A[ni][nj] = -1;
                            q.offer(new int[]{ni, nj});
                        }                        
                    }
                }
            }            
            step++;
        }        
        return -1;
    }
}