1
class Solution {
2
 public:
3
  void findOneIsland(vector<vector<int>> &grid, int i, int j, queue<pair<int, int>> &q) {
4
    if (i < 0 || j < 0 || i == grid.size() || j == grid.size() || grid[i][j] != 1) return;
5
    grid[i][j] = 2;
6
    q.push({i, j});
7

8
    findOneIsland(grid, i, j - 1, q);
9
    findOneIsland(grid, i, j + 1, q);
10
    findOneIsland(grid, i - 1, j, q);
11
    findOneIsland(grid, i + 1, j, q);
12
  }
13
  int shortestBridge(vector<vector<int>> &grid) {
14
    int n = grid.size();
15
    queue<pair<int, int>> q;
16
    int res = 0;
17
    bool OneIslandFound = false;
18
    for (int i = 0; i < n; i++) {
19
      for (int j = 0; j < n; j++) {
20
        if (grid[i][j] == 1) {
21
          OneIslandFound = true;
22
          findOneIsland(grid, i, j, q);
23
          break;
24
        }
25
      }
26
      if (OneIslandFound) break;
27
    }
28

29
    while (!q.empty()) {
30
      int i = q.front().first, j = q.front().second;
31
      q.pop();
32
      if (i != 0 && grid[i - 1][j] < 2) {
33
        if (grid[i - 1][j] == 1) {
34
          res = grid[i][j] - 2;
35
          break;
36
        }
37
        if (grid[i - 1][j] == 0) {
38
          grid[i - 1][j] = grid[i][j] + 1;
39
          q.push({i - 1, j});
40
        }
41
      }
42

43
      if (i != grid.size() - 1 && grid[i + 1][j] < 2) {
44
        if (grid[i + 1][j] == 1) {
45
          res = grid[i][j] - 2;
46
          break;
47
        }
48
        if (grid[i + 1][j] == 0) {
49
          grid[i + 1][j] = grid[i][j] + 1;
50
          q.push({i + 1, j});
51
        }
52
      }
53

54
      if (j != 0 && grid[i][j - 1] < 2) {
55
        if (grid[i][j - 1] == 1) {
56
          res = grid[i][j] - 2;
57
          break;
58
        }
59
        if (grid[i][j - 1] == 0) {
60
          grid[i][j - 1] = grid[i][j] + 1;
61
          q.push({i, j - 1});
62
        }
63
      }
64

65
      if (j != grid.size() - 1 && grid[i][j + 1] < 2) {
66
        if (grid[i][j + 1] == 1) {
67
          res = grid[i][j] - 2;
68
          break;
69
        }
70
        if (grid[i][j + 1] == 0) {
71
          grid[i][j + 1] = grid[i][j] + 1;
72
          q.push({i, j + 1});
73
        }
74
      }
75
    }
76
    return res;
77
  }
78
};