[ C++] | Basic DFS + BFS | Easy Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nLets solve this question backwards\n\nAll the elements at 0th Row and 0th Col can Fall 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLets solve this question backwards\n\nAll the elements at `0th Row` and `0th Col` can Fall into `Pacific`\nAll the elements at `M-1 th Row` and `N-1 th Col` can Fall into `Atlantic`\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nInstead of Traversing from Highest Level to Lower, Use Lower to Higher\nmeaning `Heights[row][col] <= Heights[nrow][ncol]`.\n\nFind all the elements that can be visited and if the element is visited by Both `Atlantic` and `Pacific` Coast then push it in answer\n\n\n# DFS\n```\nclass Solution {\npublic:\n    vector<int> delRow = {1,0,-1,0};\n    vector<int> delCol = {0,1,0,-1};\n    int m,n;\n     void AtlanticFlow(vector<vector<int>>& heights, int row, int col, vector<vector<bool>>& atlantic){\n          atlantic[row][col] = true;\n          for(int i = 0;i<4;i++){\n            int nrow = delRow[i]+row;\n             int ncol = delCol[i]+col;\n             if(nrow >=0 and ncol >=0 and nrow <m and ncol <n and !atlantic[nrow][ncol] and heights[row][col]<=heights[nrow][ncol]){\n               AtlanticFlow(heights, nrow, ncol,atlantic);\n             }\n          }\n     }\n       void PacificFlow(vector<vector<int>>& heights, int row, int col, vector<vector<bool>>& pacific){\n          pacific[row][col] = true;\n          for(int i = 0;i<4;i++){\n            int nrow = delRow[i]+row;\n             int ncol = delCol[i]+col;\n             if(nrow >=0 and ncol >=0 and nrow <m and ncol <n and !pacific[nrow][ncol] and heights[row][col]<=heights[nrow][ncol]){\n               PacificFlow(heights, nrow, ncol,pacific);\n             }\n          }\n     }\n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {\n         m = heights.size();\n         n = heights[0].size();\n        vector<vector<int>> ans;\n        vector<vector<bool>> pacific(m, vector<bool>(n,false));\n        vector<vector<bool>> atlantic(m, vector<bool>(n,false));\n \n        for(int i = 0;i<m;i++){\n             AtlanticFlow(heights, i, n-1, atlantic);\n             PacificFlow(heights, i, 0, pacific);\n        }\n        for(int j = 0; j<n; j++){\n            AtlanticFlow(heights, m-1, j, atlantic);\n             PacificFlow(heights, 0, j, pacific);\n        }\n     \n       for(int i = 0;i<m;i++){\n           for(int j = 0; j< n ; j++){\n               if(atlantic[i][j] and pacific[i][j]){\n                   ans.push_back({i,j});\n               }\n           }\n       }\n        \n        return ans;\n    }\n};\n```\n\n# BFS\n```\nclass Solution {\npublic:\n    vector<int> delRow = {1,0,-1,0};\n    vector<int> delCol = {0,1,0,-1};\n    int m,n;\n    \n    void bfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, queue<pair<int, int>>& q) {\n        while(!q.empty()) {\n            pair<int, int> curr = q.front();\n            q.pop();\n            for(int i=0; i<4; i++) {\n                int r = curr.first + delRow[i];\n                int c = curr.second + delCol[i];\n                if(r>=0 && c>=0 && r<m && c<n && !visited[r][c] && heights[r][c] >= heights[curr.first][curr.second]) {\n                    visited[r][c] = true;\n                    q.push(make_pair(r, c));\n                }\n            }\n        }\n    }\n    \n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {\n        m = heights.size();\n        n = heights[0].size();\n        vector<vector<int>> ans;\n        vector<vector<bool>> pacific(m, vector<bool>(n,false));\n        vector<vector<bool>> atlantic(m, vector<bool>(n,false));\n        \n        queue<pair<int, int>> pq;\n        queue<pair<int, int>> aq;\n        \n        // First and Last row\n        for(int i=0; i<n; i++) {\n            pq.push(make_pair(0, i));\n            aq.push(make_pair(m-1, i));\n        }\n        // First and Last column\n        for(int i=0; i<m; i++) {\n            pq.push(make_pair(i, 0));\n            aq.push(make_pair(i, n-1));\n        }\n        \n        bfs(heights, pacific, pq);\n        bfs(heights, atlantic, aq);\n        \n        for(int i=0; i<m; i++) {\n            for(int j=0; j<n; j++) {\n                if(pacific[i][j] && atlantic[i][j]) {\n                    ans.push_back({i, j});\n                }\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```\n
['Depth-First Search', 'Breadth-First Search', 'Matrix', 'C++']