# 46 ms C++ BFS Solution

• Two vectors that store expansion from each ocean.
Return the intersections of those two vectors.

``````class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int>> res;
int m = matrix.size();
if (m == 0) return res;
int n = matrix[0].size();

vector<vector<int>> atop(m,vector<int>(n,0));
vector<vector<int>> ptoa(m,vector<int>(n,0));

pathAP(atop, matrix);
pathPA(ptoa, matrix);

checkpair(atop, ptoa, res);
return res;
}

void checkpair(vector<vector<int>> &atop, vector<vector<int>> &ptoa, vector<pair<int,int>>& res) {
for (int i = 0; i < atop.size(); ++i) {
for (int j = 0; j < atop[0].size(); ++j) {
if (atop[i][j] == 1 && ptoa[i][j] == 1) {
res.push_back(make_pair(i,j));
}
}
}
}

void pathAP(vector<vector<int>> &atop, vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
for (int i = 0; i < matrix.size(); ++i) {
bfs(atop, matrix, visited, i, 0);
}
for (int j = 0; j < matrix[0].size(); ++j) {
bfs(atop, matrix, visited, 0, j);
}
updatePath(atop, visited);
}

void pathPA(vector<vector<int>> &ptoa, vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
for (int i = 0; i < matrix.size(); ++i) {
bfs(ptoa, matrix, visited, i, matrix[0].size()-1);
}

for (int j = 0; j < matrix[0].size(); ++j) {
bfs(ptoa, matrix, visited, matrix.size()-1, j);
}

updatePath(ptoa, visited);

}

void bfs(vector<vector<int>> &ptoa, vector<vector<int>>& matrix, vector<vector<bool>>& visited, int row, int col) {
visited[row][col] = true;

int curr = matrix[row][col];
if (row > 0 && !visited[row-1][col] && matrix[row-1][col] >= curr) bfs(ptoa, matrix, visited, row-1, col);
if (col > 0 && !visited[row][col-1]  && matrix[row][col-1] >= curr) bfs(ptoa, matrix, visited, row, col-1);
if (row < matrix.size() -1 && !visited[row+1][col] && matrix[row+1][col] >= curr) bfs(ptoa, matrix, visited, row+1, col);
if (col < matrix[0].size() -1 && !visited[row][col+1] && matrix[row][col+1] >= curr) bfs(ptoa, matrix, visited, row, col+1);
}

void updatePath(vector<vector<int>> &board, vector<vector<bool>>& visited) {
for (int i = 0; i < visited.size(); ++i) {
for (int j = 0; j < visited[0].size(); ++j) {
if (visited[i][j] && board[i][j] == 0) {
board[i][j] = 1;
}
}
}
}
};
``````

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