Straightforward efficient C++ solution using stack
The code is rather long, but very easy to understand.\nBasically, we use two tables to record if the water can flow to pacific or atlantic. To determine the ele
The code is rather long, but very easy to understand.\nBasically, we use two tables to record if the water can flow to pacific or atlantic. To determine the element, we use a stack structure to search the element on the four sides of a certain element.\nIn the test the runtime is 55ms.\n```\nclass Solution {\npublic:\n    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {\n        vector<pair<int,int>> result;\n        int m=matrix.size();\n        if (m==0) return result;\n        int n=matrix[0].size();\n        int pacific[m][n];\n        int atlantic[m][n];\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                pacific[i][j]=0;\n                atlantic[i][j]=0;\n            }\n        }\n        stack<pair<int,int>> sp;\n        stack<pair<int,int>> sa;\n        for (int i=0;i<m;i++){\n            pacific[i][0]=1;\n            sp.push(make_pair(i,0));\n        }\n        for(int i=1;i<n;i++){\n            pacific[0][i]=1;\n            sp.push(make_pair(0,i));\n        }\n        while(!sp.empty()){\n            pair<int, int> index=sp.top();\n            int x=index.first;\n            int y=index.second;\n            sp.pop();\n            if (x-1>=0&&pacific[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){\n                sp.push(make_pair(x-1,y));\n                pacific[x-1][y]=1;\n            }\n            if (x+1<m&&pacific[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){\n                sp.push(make_pair(x+1,y));\n                pacific[x+1][y]=1;\n            }\n            if (y-1>=0&&pacific[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){\n                sp.push(make_pair(x,y-1));\n                pacific[x][y-1]=1;\n            }\n            if (y+1<n&&pacific[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){\n                sp.push(make_pair(x,y+1));\n                pacific[x][y+1]=1;\n            }\n        }\n        for (int i=0;i<m;i++){\n            atlantic[i][n-1]=1;\n            sa.push(make_pair(i,n-1));\n        }\n        for(int i=0;i<n-1;i++){\n            atlantic[m-1][i]=1;\n            sa.push(make_pair(m-1,i));\n        }\n        while(!sa.empty()){\n            pair<int, int> index=sa.top();\n            int x=index.first;\n            int y=index.second;\n            sa.pop();\n            if (x-1>=0&&atlantic[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){\n                sa.push(make_pair(x-1,y));\n                atlantic[x-1][y]=1;\n            }\n            if (x+1<m&&atlantic[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){\n                sa.push(make_pair(x+1,y));\n                atlantic[x+1][y]=1;\n            }\n            if (y-1>=0&&atlantic[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){\n                sa.push(make_pair(x,y-1));\n                atlantic[x][y-1]=1;\n            }\n            if (y+1<n&&atlantic[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){\n                sa.push(make_pair(x,y+1));\n                atlantic[x][y+1]=1;\n            }\n        }\n        for(int i=0; i<m;i++){\n            for(int j=0;j<n;j++){\n                if (atlantic[i][j]==1&&pacific[i][j]==1){\n                    result.push_back(make_pair(i,j));\n                }\n            }\n        }\n        return result;\n    }\n};\n\n```
[]