C++ solution with short explanation | DFS
The main idea is to try to go from the edges ("oceans") to other nodes. By keeping track of reached nodes from each "ocean" we can find the nodes which can reac
The main idea is to try to go from the edges ("oceans") to other nodes. By keeping track of reached nodes from each "ocean" we can find the nodes which can reach both oceans.\n\n```\nclass Solution {\nprivate:\n    void dfs(const vector<vector<int>>& matrix, const vector<pair<int, int>> &coords, vector<vector<bool>> &visited, int i, int j) {\n        visited[i][j] = true;\n        \n        for(auto &coord : coords) {\n            int next_i = coord.first + i;\n            int next_j = coord.second + j;\n            \n\t\t\t// since we\'re going backwards (from "ocean" instead of to) we want the next node\'s value to be equal to or more than the current node\'s value\n            if (is_in_bounds(matrix, next_i, next_j) && !visited[next_i][next_j] && matrix[next_i][next_j] >= matrix[i][j]) {\n                dfs(matrix, coords, visited, next_i, next_j);\n            }\n        }\n    }\n    \n    bool is_in_bounds(const vector<vector<int>>& matrix, int i, int j) {\n        return i >= 0 && j >= 0 && i < matrix.size() && j < matrix[0].size();\n    }\n    \npublic:\n    vector<vector<int>> pacificAtlantic(const vector<vector<int>>& matrix) {\n        if (matrix.empty())\n            return vector<vector<int>>();\n        \n        const vector<pair<int, int>> coords = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};\n        \n        int n = matrix.size(), m = matrix[0].size();\n        vector<vector<bool>> visited_atlantic(n, vector<bool>(m, false));\n        vector<vector<bool>> visited_pacific(n, vector<bool>(m, false));\n        \n        for(int i = 0; i < n; i++) {\n\t\t    // left edge for pacific ocean\n            dfs(matrix, coords, visited_pacific, i, 0);\n\t\t    // right edge for atlantic ocean\n            dfs(matrix, coords, visited_atlantic, i, m - 1);\n        }\n        for(int j = 0; j < m; j++) {\n            // top edge for pacific ocean\n            dfs(matrix, coords, visited_pacific, 0, j);\n\t\t\t// bottom edge for atlantic ocean\n            dfs(matrix, coords, visited_atlantic, n - 1, j);\n        }\n        \n        vector<vector<int>> result;\n\t\t// find the nodes that can reach both oceans\n        for(int i = 0; i < n; i++)\n            for(int j = 0; j < m; j++)\n                if (visited_pacific[i][j] && visited_atlantic[i][j])\n                    result.push_back({ i, j });\n        \n        return result;\n    }\n};\n\n\n\n\n\n\n\n\n```
['Depth-First Search', 'C']