aboutsummaryrefslogtreecommitdiff
path: root/shortest_bridge.cpp
blob: 818d384f3cbe9916d98ee288299271ac0e2dfc9e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 934. Shortest Bridge
#include "leetcode.h"

/*
 * given an 'n x n' binary matrix grid where 1 represents land and 0 represents
 * water. an island is a 4 directionally connected group of 1's not connected to
 * any other 1's. there are exactly two islands in a 'grid'. you may change 0's
 * to 1's to connect the two islands to form one island. return the smallest
 * numbe of 0's you must flip to connect the two islands.
 */

class Solution {
  queue<pair<int, int>> qp;
  void dfs(vvd & grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() ||
        grid[i][j] == 2 || !grid[i][j])
      return;
    grid[i][j] = 2;
    qp.push({i, j});
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
  }
  int bfs(vvd & grid) {
    int d = 0, min_dist = INT_MAX;
    vvd dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while (!qp.empty()) {
      int n = qp.size();
      while (n--) {
        auto a = qp.front();
        qp.pop();
        for (int h = 0; h < 4; h++) {
          int x = dir[h][0] + a.first;
          int y = dir[h][1] + a.second;
          if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
              grid[x][y])
            min_dist = min(min_dist, d);
          else if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
                   !grid[x][y]) {
            qp.push({x, y});
            grid[x][y] = 2;
          }
        }
      }
      d++;
    }
    return min_dist;
  }

public:
  int shotestBridge(vvd & grid) {
    bool flag = false;
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] && !flag) {
          dfs(grid, i, j);
          qp.push({i, j});
          flag = true;
          break;
        }
      }
      if (flag)
        break;
    }
    return bfs(grid);
  }
};

int main() {
  Solution obj;
  vvd g1 = {{0, 1}, {1, 0}};
  vvd g2 = {{0, 1, 0}, {0, 0, 0}, {0, 0, 1}};
  vvd g3 = {{1, 1, 1, 1, 1},
                 {1, 0, 0, 0, 1},
                 {1, 0, 1, 0, 1},
                 {1, 0, 0, 0, 1},
                 {1, 1, 1, 1, 1}};
  printf("%d\n", obj.shotestBridge(g1)); // expect: 1
  printf("%d\n", obj.shotestBridge(g2)); // expect: 2
  printf("%d\n", obj.shotestBridge(g3)); // expect: 1
}