934. Shortest Bridge

Posted on Edited on In

934. Shortest Bridge

Description

You are 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 grid.

You may change 0‘s to 1‘s to connect the two islands to form one island .

Return the smallest number of 0‘s you must flip to connect the two islands.

Example 1:

1
2
Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

1
2
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

1
2
Input: grid = [[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]]
Output: 1

Constraints:

  • n == grid.length == grid[i].length
  • 2 <= n <= 100
  • grid[i][j] is either 0 or 1.
  • There are exactly two islands in grid.

Hints/Notes

Solution

Language: C++

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
class Solution {
public:
    static constexpr int DIRs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    int shortestBridge(vector<vector<int>>& grid) {
        // find one island, then bfs
        queue<pair<int, int>> islandOne;
        int m = grid.size(), n = grid[0].size();
        bool not_marked = true;
        for (int i = 0; i < m && not_marked; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue<pair<int, int>> q;
                    q.emplace(i, j);
                    islandOne.emplace(i, j);
                    grid[i][j] = -1;
                    while (!q.empty()) {
                        auto [x, y] = q.front();
                        q.pop();
                        for (int k = 0; k < 4; k++) {
                            int dx = x + DIRs[k][0], dy = y + DIRs[k][1];
                            if (dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == 1) {
                                grid[dx][dy] = -1;
                                q.emplace(dx, dy);
                                islandOne.emplace(dx, dy);
                            }
                        }
                    }
                    not_marked = false;
                    break;
                }
            }
        }
        int step = 0;
        while (!islandOne.empty()) {
            int size = islandOne.size();
            for (int i = 0; i < size; i++) {
                auto [x, y] = islandOne.front();
                islandOne.pop();
                for (int k = 0; k < 4; k++) {
                    int dx = x + DIRs[k][0], dy = y + DIRs[k][1];
                    if (dx >= 0 && dx < m && dy >= 0 && dy < n) {
                        if (grid[dx][dy] == 1) {
                            return step;
                        } else if (grid[dx][dy] == 0) {
                            grid[dx][dy] = -1;
                            islandOne.emplace(dx, dy);
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};