# Leetcode 417 Solution

https://leetcode.com/problems/pacific-atlantic-water-flow

## Solution

``````class Solution {
public:
void fill(vector<vector<int>>& matrix, vector<vector<int>>& a, queue<pair<int, int>>& q, int m, int n)
{
while (q.empty() == false)
{
auto pair = q.front();
q.pop();
int i = pair.first;
int j = pair.second;

if (i < m - 1 && matrix[i][j] <= matrix[i + 1][j])
{
if (a[i + 1][j] == 0)
{
a[i + 1][j] = 1;
q.push(make_pair(i + 1, j));
}
}

if (j < n - 1 && matrix[i][j] <= matrix[i][j + 1])
{
if (a[i][j + 1] == 0)
{
a[i][j + 1] = 1;
q.push(make_pair(i, j + 1));
}
}

if (i > 0 && matrix[i][j] <= matrix[i - 1][j])
{
if (a[i - 1][j] == 0)
{
a[i - 1][j] = 1;
q.push(make_pair(i - 1, j));
}
}

if (j > 0 && matrix[i][j] <= matrix[i][j - 1])
{
if (a[i][j - 1] == 0)
{
a[i][j - 1] = 1;
q.push(make_pair(i, j - 1));
}
}
}
}

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int, int>> res;

if (matrix.size() == 0)
return res;

int m = matrix.size();
int n = matrix[0].size();

vector<vector<int>> a(m, vector<int>(n));
vector<vector<int>> b(m, vector<int>(n));

queue<pair<int, int>> q;

for (int i = 0; i < m; i++)
a[i][0] = 1, q.push(make_pair(i, 0));
for (int j = 0; j < n; j++)
a[0][j] = 1, q.push(make_pair(0, j));

fill(matrix, a, q, m, n);

for (int i = 0; i < m; i++)
b[i][n - 1] = 1, q.push(make_pair(i, n - 1));
for (int j = 0; j < n; j++)
b[m - 1][j] = 1, q.push(make_pair(m - 1, j));

fill(matrix, b, q, m, n);

for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] && b[i][j])
res.push_back(make_pair(i, j));
}
}

return res;
}
};
``````