C++ BFS simple solution


  • 0
    class Solution {
    public:
        void bfs(vector<vector<int>>& matrix, int row, int col, vector<vector<int>>& record, int sea) {
            queue<pair<int, int>> qu;
            qu.push({row, col});
            vector<pair<int, int>> nei = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
            while (qu.size()) {
                pair<int, int> cur = qu.front();
                qu.pop();
                if (record[cur.first][cur.second] == (record[cur.first][cur.second] | sea))
                    continue;
                record[cur.first][cur.second] |= sea;
                for (auto n : nei) {
                    int r = cur.first + n.first, c = cur.second + n.second;
                    if (r >= 0 && r < matrix.size() && c >= 0 && c < matrix[0].size() &&
                        matrix[cur.first][cur.second] <= matrix[r][c])
                        qu.push({r, c});
                }
            }
        }
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            int m = matrix.size(), n = m ? matrix[0].size() : 0;
            vector<pair<int, int>> res;
            if (!n)
                return res;
            vector<vector<int>> record(m, vector<int>(n, 0));
            for (int i = 0; i < m; i++) {
                bfs(matrix, i, 0, record, 1);
                bfs(matrix, i, n - 1, record, 2);
            }
            for (int i = 0; i < n; i++) {
                bfs(matrix, 0, i, record, 1);
                bfs(matrix, m - 1, i, record, 2);
            }
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (record[i][j] == 3)
                        res.push_back({i, j});
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.