# C++ BFS 53ms

• ``````class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
int m = (int) matrix.size(), n = (int) matrix[0].size();
int pm[m][n];
fill_n(&pm[0][0], m * n, false);
int am[m][n];
fill_n(&am[0][0], m * n, false);
queue<pair<int, int>> pq; // next point for pacific bfs;
queue<pair<int, int>> aq; // next point for atlantic bfs;
vector<pair<int, int>> res;
for (int i = 0; i < m; i++) {
int j = m - i - 1;
pm[i][0] = 1;
pq.push({i, 0});
am[j][n-1] = 1;
aq.push({j, n-1});
}
for (int i = 1; i < n; i++) {
int j = n - i - 1;
pm[0][i] = 1;
pq.push({0, i});
am[m-1][j] = 1;
aq.push({m-1, j});
}
while (!pq.empty()) {
pair<int, int> point = pq.front();
int x = point.first, y = point.second;
pq.pop();
if (x-1 >= 0 && !pm[x-1][y] && matrix[x-1][y] >= matrix[x][y]) {
pq.push({x-1, y});
pm[x-1][y] = 1;
}
if (x+1 < m && !pm[x+1][y] && matrix[x+1][y] >= matrix[x][y]) {
pq.push({x+1, y});
pm[x+1][y] = 1;
}
if (y-1 >= 0 && !pm[x][y-1] && matrix[x][y-1] >= matrix[x][y]) {
pq.push({x, y-1});
pm[x][y-1] = 1;
}
if (y+1 < n && !pm[x][y+1] && matrix[x][y+1] >= matrix[x][y]) {
pq.push({x, y+1});
pm[x][y+1] = 1;
}
}
while (!aq.empty()) {
pair<int, int> point = aq.front();
int x = point.first, y = point.second;
if (am[x][y] && pm[x][y]) res.push_back({x,y});
aq.pop();
if (x-1 >= 0 && !am[x-1][y] && matrix[x-1][y] >= matrix[x][y]) {
aq.push({x-1, y});
am[x-1][y] = 1;
}
if (x+1 < m && !am[x+1][y] && matrix[x+1][y] >= matrix[x][y]) {
aq.push({x+1, y});
am[x+1][y] = 1;
}
if (y-1 >= 0 && !am[x][y-1] && matrix[x][y-1] >= matrix[x][y]) {
aq.push({x, y-1});
am[x][y-1] = 1;
}
if (y+1 < n && !am[x][y+1] && matrix[x][y+1] >= matrix[x][y]) {
aq.push({x, y+1});
am[x][y+1] = 1;
}
}
return res;
}
};
``````

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