C++ BFS simple solution

• ``````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;
}
};
``````

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