# C++ BFS flood 55ms 97%

• ``````class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int, int>> ans;
if(matrix.empty() || matrix[0].empty()) return ans;
int r = matrix.size(), c = matrix[0].size();
vector<vector<int>>pac(r, vector<int>(c,0));
auto atl = pac;
deque<pair<int,int>>aq,pq;

for(int i = 0; i < r; i++)
{
atl[i][c-1] = pac[i][0] = 1;
aq.push_back(make_pair(i,c-1));
pq.push_back(make_pair(i,0));
}

for(int i = 0; i < c; i++)
{
atl[r-1][i] = pac[0][i] = 1;
aq.push_back(make_pair(r-1,i));
pq.push_back(make_pair(0,i));
}

while(!aq.empty())
{
int m = aq.front().first;
int n = aq.front().second;
aq.pop_front();
if(m>0 && atl[m-1][n] == 0 && matrix[m-1][n]>=matrix[m][n])
{
atl[m-1][n] = 1;
aq.push_back(make_pair(m-1,n));
}

if(n>0 && atl[m][n-1] == 0 && matrix[m][n-1]>=matrix[m][n])
{
atl[m][n-1] = 1;
aq.push_back(make_pair(m,n-1));
}

if(m+1 < r && atl[m+1][n] == 0 && matrix[m+1][n]>=matrix[m][n])
{
atl[m+1][n] = 1;
aq.push_back(make_pair(m+1,n));
}

if(n+1 < c && atl[m][n+1] == 0 && matrix[m][n+1]>=matrix[m][n])
{
atl[m][n+1] = 1;
aq.push_back(make_pair(m,n+1));
}
}

while(!pq.empty())
{
int m = pq.front().first;
int n = pq.front().second;
pq.pop_front();
if(m>0 && pac[m-1][n] == 0 && matrix[m-1][n]>=matrix[m][n])
{
pac[m-1][n] = 1;
pq.push_back(make_pair(m-1,n));
}

if(n>0 && pac[m][n-1] == 0 && matrix[m][n-1]>=matrix[m][n])
{
pac[m][n-1] = 1;
pq.push_back(make_pair(m,n-1));
}

if(m+1 < r && pac[m+1][n] == 0 && matrix[m+1][n]>=matrix[m][n])
{
pac[m+1][n] = 1;
pq.push_back(make_pair(m+1,n));
}

if(n+1 < c && pac[m][n+1] == 0 && matrix[m][n+1]>=matrix[m][n])
{
pac[m][n+1] = 1;
pq.push_back(make_pair(m,n+1));
}
}

for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
if(atl[i][j] && pac[i][j]) ans.push_back(make_pair(i,j));

return ans;
}
};``````

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