934 shortest bridge

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.)

 

Example 1:

Input: A = [[0,1],[1,0]]
Output: 1

Example 2:

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

Example 3:

Input: A = [[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:

• 2 <= A.length == A[0].length <= 100
• A[i][j] == 0 or A[i][j] == 1

class Solution {

public:

    int shortestBridge(vector<vector<int>>& A) {

        int rows = A.size();

        int cols;

        if (rows == 0) {

            return 0;

        }

        cols = A[0].size();

        queue<pair<int, int>> q;

        bool found = false;

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (A[i][j] == 1) {

                    dfs(A, i, j, q);

                    found = true;

                    break;

                }

            }

            if (found) {

                break;

            }

        }

        

        int ans = 0;

        vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        while (!q.empty()) {

            int size = q.size();

            while (size != 0) {

                size--;

                auto point = q.front(); q.pop();

                for (auto dir : dirs) {

                    pair<int, int> new_point = {point.first + dir[0], point.second + dir[1]};

                    if (!valid(new_point, rows, cols)) {

                        continue;

                    }

                    if (A[new_point.first][new_point.second] == 2) {

                        continue;

                    } else if (A[new_point.first][new_point.second] == 1) {

                        return ans;

                    }

                    A[new_point.first][new_point.second] = 2;

                    q.push(new_point);   

                }

            }

            ans++;

        }

        return ans;

    }

    

    bool valid(pair<int, int> point, int rows, int cols) {

        if (point.first < 0 || point.second < 0 || point.first >= rows || point.second >= cols) {

            return false;

        }

        return true;

    }

    

    void dfs(vector<vector<int>>& A, int i, int j, queue<pair<int, int>>& q) {

        if (i < 0 || i >= A.size() || j < 0 || j >= A[0].size() || A[i][j] != 1) {

            return;

        }

        A[i][j] = 2;

        q.push({i, j});

        dfs(A, i + 1, j, q);

        dfs(A, i - 1, j, q);

        dfs(A, i, j + 1, q);

        dfs(A, i, j - 1, q);

    }

};