1
/**
2
 * @param {number[][]} grid
3
 * @return {number}
4
 */
5
const DIR = [
6
  [0, 1],
7
  [0, -1],
8
  [1, 0],
9
  [-1, 0],
10
];
11

12
var shortestBridge = function (grid) {
13
  const que = [];
14
  const ROWS = grid.length;
15
  const COLS = grid[0].length;
16

17
  // find first insland
18
  outer: for (let row = 0; row < ROWS; row++) {
19
    for (let col = 0; col < COLS; col++) {
20
      if (grid[row][col] == 1) {
21
        const stack = [[row, col]];
22
        while (stack.length) {
23
          const [r, c] = stack.pop();
24
          que.push([r, c]);
25
          grid[r][c] = 2; // mark as visited.
26
          for (const dir of DIR) {
27
            const newRow = r + dir[0];
28
            const newCol = c + dir[1];
29
            if (newRow < 0 || newCol < 0 || newRow >= ROWS || newCol >= COLS)
30
              continue;
31
            if (grid[newRow][newCol] != 1) continue;
32
            stack.push([newRow, newCol]);
33
          }
34
        }
35
        break outer;
36
      }
37
    }
38
  }
39
  let steps = 0;
40
  while (que.length) {
41
    let size = que.length;
42
    for (let i = 0; i < size; i++) {
43
      const [row, col] = que.shift();
44
      for (const dir of DIR) {
45
        const newRow = row + dir[0];
46
        const newCol = col + dir[1];
47
        if (newRow < 0 || newCol < 0 || newRow >= ROWS || newCol >= COLS)
48
          continue;
49
        if (grid[newRow][newCol] == 2) continue;
50
        if (grid[newRow][newCol] == 1) return steps;
51
        grid[newRow][newCol] = 2; // mark as visited.
52
        que.push([newRow, newCol]);
53
      }
54
    }
55
    steps++;
56
  }
57
  return -1;
58
};