[leetcode]934. Shortest Bridge

Analysis

2019要开心鸭—— [每天刷题并不难0.0]

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Explanation:

先用DFS标记island，再用BFS扩充island，从而找到bridge的数量

Implement

class Solution {
public:
    int shortestBridge(vector<vector<int>>& A) {
        pair<int, int> start;
        m = A.size();
        n = A[0].size();
        vector<vector<int>> visit(m, vector<int>(n));
        queue<pair<int, int>> mq;
        int flag = 0;
        
        for(int i=0; i<m; i++){
            if(flag == 1)
                break;
            for(int j=0; j<n; j++){
                if(A[i][j] == 1){
                    DFS(i, j, A, visit, mq);
                    flag = 1;
                    break;
                }
            }
        }
        //DFS(start.first, start.second, A, visit, mq);
        int res = 0;
        while(!mq.empty()){
            int sz = mq.size();
            while(sz-- > 0){
                pair<int, int> cur = mq.front();
                mq.pop();
                for(int i=0; i<4; i++){
                    int x = cur.first+dir[i][0];
                    int y = cur.second+dir[i][1];
                    if(x>=0 && y>=0 && x<m && y<n && visit[x][y]==0){
                        if(A[x][y] == 1)
                            return res;
                        visit[x][y] = 1;
                        mq.emplace(x, y);
                    }
                   
                }
            }
            res++;
        }
        return -1;
    }
    void DFS(int x, int y, vector<vector<int>>& A, vector<vector<int>>& visit, queue<pair<int, int>>& mq){
        if(x<0 || x>=m || y<0 || y>=n || visit[x][y]==1 || A[x][y]==0)
            return ;
        visit[x][y] = 1;
        mq.emplace(x, y);
        for(int i=0; i<4; i++)
            DFS(x+dir[i][0], y+dir[i][1], A, visit, mq);
    }
private:
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m, n;
};