```
public class Solution {
public int[,] mat; public int m; public int n;
public bool[,] processing;
public IList<int[]> PacificAtlantic(int[,] matrix) {
var result = new List<int[]>();
if (matrix == null) { return result; }
mat = matrix; m = mat.GetLength(0); n = mat.GetLength(1); processing = new bool[m, n];
//left and up flow into atlantic; right and down flow into pacific -- unlike the above picture
for (int i = m - 1; i >= 0; i--) { // start from bottom left or top right
for (int j = 0; j < n; j++) {
if (canFlowBothWays(i, j)) {
result.Add(new[] { i, j });
}
}
}
return result;
}
public bool canFlowToAtlantic(int i, int j) {
if (processing[i, j]) { return false; }
processing[i, j] = true;
bool left = false, up = false;
left = j - 1 < 0 ? true : mat[i, j - 1] <= mat[i, j] ? canFlowToAtlantic(i, j - 1) : false;
if (!left) {
up = i - 1 < 0 ? true : mat[i - 1, j] <= mat[i, j] ? canFlowToAtlantic(i - 1, j) : false;
}
if (!up && !left) { // if both up and left are false, now it is time to go right and repeat above, because there could be a
// path from the right and that may end up left or up
bool canflow;
if (j + 1 < n && mat[i, j + 1] <= mat[i, j]) { // go right
canflow = canFlowToAtlantic(i, j + 1);
processing[i, j] = false;
if (canflow) { // if there is a path, then return and no need to check the path from down
return canflow;
}
}
if(i + 1 < m && mat[i + 1, j] <= mat[i, j]) { //go down
canflow = canFlowToAtlantic(i + 1, j);
processing[i, j] = false;
return canflow;
}
}
processing[i, j] = false;
return left || up; // all the while we only check if water can flow to atlantic in this method
}
public bool canFlowToPacific(int i, int j) {
if (processing[i, j]) { return false; }
processing[i, j] = true;
bool down = false, right = false;
down = i + 1 >= m ? true : mat[i + 1, j] <= mat[i, j] ? canFlowToPacific(i + 1, j) : false;
if (!down) {
right = j + 1 >= n ? true : mat[i, j + 1] <= mat[i, j] ? canFlowToPacific(i, j + 1) : false;
}
if (!down && !right) {
bool canflow;
if (j - 1 >= 0 && mat[i, j - 1] <= mat[i, j]) {
canflow = canFlowToPacific(i, j - 1); // check if there is a path from left
processing[i, j] = false;
if (canflow) {
return canflow;
}
}
if(i - 1 >= 0 && mat[i - 1, j] <= mat[i, j]){
var canFlow = canFlowToPacific(i - 1, j); // check if there is a path from up
processing[i, j] = false;
return canFlow;
}
}
processing[i, j] = false;
return down || right; //all the while we only check if water can flow to pacific in this method
}
public bool canFlowBothWays(int i, int j) {
return canFlowToAtlantic(i, j) && canFlowToPacific(i, j);
}
}
```