1
class Solution {
2
  private static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
3

4
  public int shortestBridge(int[][] grid) {
5
    boolean[][] visited = new boolean[grid.length][grid[0].length];
6
    LinkedList<Pair> queue = new LinkedList<Pair>();
7
    boolean found = false;
8
    for (int i = 0; i < grid.length && !found; i++) {
9
      for (int j = 0; j < grid[0].length && !found; j++) {
10
        if (grid[i][j] == 1) {
11
          dfs(grid, i, j, queue, visited);
12
          found = true;
13
        }
14
      }
15
    }
16
    int level = 0;
17
    while (queue.size() > 0) {
18
      int size = queue.size();
19
      while (size-- > 0) {
20
        Pair pair = queue.poll();
21
        for (int k = 0; k < 4; k++) {
22
          int rowDash = pair.row + dirs[k][0];
23
          int colDash = pair.col + dirs[k][1];
24
          if (rowDash < 0
25
              || colDash < 0
26
              || rowDash >= grid.length
27
              || colDash >= grid[0].length
28
              || visited[rowDash][colDash] == true) continue;
29
          if (grid[rowDash][colDash] == 1) return level;
30
          queue.add(new Pair(rowDash, colDash));
31
          visited[rowDash][colDash] = true;
32
        }
33
      }
34
      level++;
35
    }
36
    return -1;
37
  }
38

39
  private void dfs(int[][] grid, int i, int j, LinkedList<Pair> queue, boolean[][] visited) {
40
    visited[i][j] = true;
41
    queue.add(new Pair(i, j));
42
    for (int k = 0; k < 4; k++) {
43
      int rowDash = i + dirs[k][0];
44
      int colDash = j + dirs[k][1];
45
      if (rowDash < 0
46
          || colDash < 0
47
          || rowDash >= grid.length
48
          || colDash >= grid[0].length
49
          || visited[rowDash][colDash] == true
50
          || grid[rowDash][colDash] == 0) continue;
51
      dfs(grid, rowDash, colDash, queue, visited);
52
    }
53
  }
54

55
  static class Pair {
56
    int row;
57
    int col;
58

59
    public Pair(int row, int col) {
60
      this.row = row;
61
      this.col = col;
62
    }
63
  }
64
}