[LeetCode The Hard Way] Easy DFS with Explanations
Please check out LeetCode The Hard Way for more solution explanations and tutorials. If you like it, please give a star and watch my Github Repository.\n\n---\n
Please check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. If you like it, please give a star and watch my [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way).\n\n---\n\n```cpp\n// https://wingkwong.github.io/leetcode-the-hard-way/solutions/0400-0499/pacific-atlantic-water-flow-medium\nclass Solution {\npublic:\n    void dfs(vector<vector<int>>& M, vector<vector<int>>& vis, int i, int j) {\n        int m = M.size(), n = M[0].size();\n        // marked this cell (i, j) as visited\n        // so that we won\'t visit it again\n        vis[i][j] = 1;\n        // perform DFS on the left cell\n        if (i - 1 >= 0 && !vis[i - 1][j] && M[i - 1][j] >= M[i][j]) dfs(M, vis, i - 1, j);\n        // perform DFS on the right cell\n        if (i + 1 < m && !vis[i + 1][j] && M[i + 1][j] >= M[i][j]) dfs(M, vis, i + 1, j);\n        // perform DFS on the top cell\n        if (j - 1 >= 0 && !vis[i][j - 1] && M[i][j - 1] >= M[i][j]) dfs(M, vis, i, j - 1);\n        // perform DFS on the bottom cell\n        if (j + 1 < n && !vis[i][j + 1] && M[i][j + 1] >= M[i][j]) dfs(M, vis, i, j + 1);\n    }\n    \n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& M) {\n        vector<vector<int>> ans;\n        int m = M.size(), n = M[0].size();\n        // P[i][j] = 1 means it is able to flow to pacific ocean\n        vector<vector<int>> P(m, vector<int>(n));\n        // A[i][j] = 1 means it is able to flow to atlantic ocean\n        vector<vector<int>> A(m, vector<int>(n));\n        for(int i = 0; i < m; i++) {\n            // perform dfs starting from the left-most column \n            dfs(M, P, i, 0);\n            // perform dfs starting from the right-most column \n            dfs(M, A, i, n - 1);\n        }\n        for(int i = 0; i < n; i++) {\n            // perform dfs starting from the top-most row\n            dfs(M, P, 0, i);\n            // perform dfs starting from the bottom-most row\n            dfs(M, A, m - 1, i);\n        }\n        // iterate each row\n        for(int i = 0; i < m; i++) {\n            // iterate each column\n            for(int j = 0; j < n; j++) {\n                // if both P[i][j] & A[i][j] are visited\n                // that means this cell can flow to both ocean\n                if(P[i][j] && A[i][j]) {\n                    // then put the coordinate (i, j) to answer\n                    ans.push_back(vector<int>{i, j});\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C', 'C++']