给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
输出坐标的顺序不重要m 和 n 都小于150
示例：
给定下面的 5x5 矩阵: 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * 大西洋 返回: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
C++
class Solution { public: void bfs(queue<pair<int,int>>& que, vector<vector<int>>& flag, vector<vector<int>>& matrix) { int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; while(!que.empty()) { auto it=que.front(); que.pop(); int i=it.first; int j=it.second; for(int k=0;k<4;k++) { int y=i+dy[k]; int x=j+dx[k]; if(y>=0 && y<matrix.size() && x>=0 && x<matrix[0].size() && 0==flag[y][x] && matrix[y][x]>=matrix[i][j]) { flag[y][x]=1; que.push({y,x}); } } } } vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) { vector<vector<int>> res; if(0==matrix.size() || 0==matrix[0].size()) { return res; } int m=matrix.size(); int n=matrix[0].size(); vector<vector<int>> flag(m,vector<int>(n,0)); queue<pair<int,int>> que; for(int i=0;i<m;i++) { flag[i][0]=1; que.push({i,0}); } for(int i=1;i<n;i++) { flag[0][i]=1; que.push({0,i}); } bfs(que,flag,matrix); vector<vector<int>> vec(m,vector<int>(n,0)); for(int i=0;i<m;i++) { vec[i][n-1]=1; que.push({i,n-1}); } for(int i=0;i<n-1;i++) { vec[m-1][i]=1; que.push({m-1,i}); } bfs(que,vec,matrix); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(flag[i][j] && vec[i][j]) { res.push_back({i,j}); } } } return res; } };
