精品推薦：

《征服數(shù)據(jù)結(jié)構(gòu)》專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

《經(jīng)典圖論算法》專欄：50多種經(jīng)典圖論算法全部掌握

在近在網(wǎng)上看到一個(gè)視頻，一HR在幫內(nèi)陸一家非常大的手機(jī)品牌在香港招聘的時(shí)候，要求年齡限制在35歲以下，引起該HR的痛批。至于是哪家手機(jī)品牌，視頻中沒(méi)有透露，我們也不要隨便猜測(cè)。只是這個(gè)行為在內(nèi)陸已經(jīng)司空見(jiàn)慣了，雖然批評(píng)的聲音一直存在，但大家好像都已經(jīng)習(xí)慣了。至于在香港應(yīng)該還沒(méi)有這方面的先例，有網(wǎng)友評(píng)論道：“過(guò)分了。內(nèi)陸大企業(yè)想把劣質(zhì)招聘文化帶到香港！必須拒絕！

--------------下面是今天的算法題--------------

來(lái)看下今天的算法題，這題是LeetCode的第417題：太平洋大西洋水流問(wèn)題。

有一個(gè) m × n 的矩形島嶼，與 太平洋 和 大西洋 相鄰。“太平洋” 處于大陸的左邊界和上邊界，而 “大西洋” 處于大陸的右邊界和下邊界。

這個(gè)島被分割成一個(gè)由若干方形單元格組成的網(wǎng)格。給定一個(gè) m x n 的整數(shù)矩陣 heights ， heights[r][c] 表示坐標(biāo) (r, c) 上單元格 高于海平面的高度 。

島上雨水較多，如果相鄰單元格的高度小于或等于當(dāng)前單元格的高度，雨水可以直接向北、南、東、西流向相鄰單元格。水可以從海洋附近的任何單元格流入海洋。

返回網(wǎng)格坐標(biāo) result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水從單元格 (ri, ci) 流動(dòng)既可流向太平洋也可流向大西洋。

輸入: heights = [[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]]

輸入: heights = [[2,1],[1,2]]

輸出: [[0,0],[0,1],[1,0],[1,1]]

public List<List<Integer>> pacificAtlantic(int[][] heights) {
 List<List<Integer>> ans = new ArrayList<>();
 int n = heights.length, m = heights[0].length;
 // 哪些位置可以到達(dá)太平洋
 boolean[][] pacific = new boolean[n][m];// 太平洋
 // 哪些位置可以到達(dá)大西洋
 boolean[][] atlantic = new boolean[n][m];// 大西洋
 Queue<int[]> pQueue = new LinkedList<>();
 Queue<int[]> aQueue = new LinkedList<>();
 // 四周邊界
 for (int i = 0; i < n; i++) {
  pQueue.offer(new int[]{i, 0});
  aQueue.offer(new int[]{i, m - 1});
  pacific[i][0] = true;
  atlantic[i][m - 1] = true;
 }
 for (int i = 0; i < m; i++) {
  pQueue.offer(new int[]{0, i});
  aQueue.offer(new int[]{n - 1, i});
  pacific[0][i] = true;
  atlantic[n - 1][i] = true;
 }
 bfs(heights, m, n, pQueue, pacific);// 先查找能夠到達(dá)太平洋的坐標(biāo)
 bfs(heights, m, n, aQueue, atlantic);// 在查找能夠達(dá)到大西洋的坐標(biāo)

 for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   // 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋
   if (pacific[i][j] && atlantic[i][j])
 ans.add(Arrays.asList(i, j));
  }
 }
 return ans;
}

int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

private void bfs(int[][] heights, int m, int n, Queue<int[]> queue, boolean[][] visited) {
 while (!queue.isEmpty()) {
  int[] cur = queue.poll();
  for (int[] d : dir) {
   int x = cur[0] + d[0];
   int y = cur[1] + d[1];
   // 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么
   // heights[x][y]的高度必須要大于[cur[0]][cur[1]]。
   if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y]
  || heights[x][y] < heights[cur[0]][cur[1]])
 continue;
   visited[x][y] = true;// 標(biāo)記可以到達(dá)
   queue.offer(new int[]{x, y});
  }
 }
}

public:
 vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
  vector<vector<int>> ans;
  int n = heights.size(), m = heights[0].size();
  // 哪些位置可以到達(dá)太平洋
  vector<vector<bool>> pacific(n, vector<bool>(m, false));
  // 哪些位置可以到達(dá)大西洋
  vector<vector<bool>> atlantic(n, vector<bool>(m, false));
  queue<pair<int, int>> pQueue;
  queue<pair<int, int>> aQueue;
  // 四周邊界
  for (int i = 0; i < n; i++) {
   pQueue.emplace(i, 0);
   aQueue.emplace(i, m - 1);
   pacific[i][0] = true;
   atlantic[i][m - 1] = true;
  }
  for (int i = 0; i < m; i++) {
   pQueue.emplace(0, i);
   aQueue.emplace(n - 1, i);
   pacific[0][i] = true;
   atlantic[n - 1][i] = true;
  }
  bfs(heights, m, n, pQueue, pacific);// 先查找能夠到達(dá)太平洋的坐標(biāo)
  bfs(heights, m, n, aQueue, atlantic);// 在查找能夠達(dá)到大西洋的坐標(biāo)

  for (int i = 0; i < n; i++) {
   for (int j = 0; j < m; j++) {
 // 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋
 if (pacific[i][j] && atlantic[i][j])
  ans.push_back({i, j});
   }
  }
  return ans;
 }

 int dir[4][2] = {{1,  0},
   {-1, 0},
   {0,  1},
   {0,  -1}};

 void bfs(vector<vector<int>> &heights, int m, int n, queue<pair<int, int>> &q, vector<vector<bool>> &visited) {
  while (!q.empty()) {
   pair<int, int> cur = q.front();
   q.pop();
   for (const auto d: dir) {
 int x = cur.first + d[0];
 int y = cur.second + d[1];
 // 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么
 // heights[x][y]的高度必須要大于[cur[0]][cur[1]]。
 if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y]
  || heights[x][y] < heights[cur.first][cur.second])
  continue;
 visited[x][y] = true;// 標(biāo)記可以到達(dá)
 q.emplace(x, y);
   }
  }
 }

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
 def bfs(q, visited):
  while q:
   cur = q.pop()
   for d in dirs:
 x = cur[0] + d[0]
 y = cur[1] + d[1]
 # 水如果從位置heights[x][y]流到位置[cur[0]][cur[1]]，那么heights[x][y] 的高度必須要大于[cur[0]][cur[1]]。
 if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or heights[x][y] < heights[cur[0]][cur[1]]:
  continue
 visited[x][y] = True  # 標(biāo)記可以到達(dá)
 q.append([x, y])

 dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
 ans = []
 n, m = len(heights), len(heights[0])
 # 哪些位置可以到達(dá)太平洋
 pacific = [[False for _ in range(m)] for _ in range(n)]
 # 哪些位置可以到達(dá)大西洋
 atlantic = [[False for _ in range(m)] for _ in range(n)]
 pQueue = []
 aQueue = []
 # 四周邊界
 for i in range(n):
  pQueue.append([i, 0])
  aQueue.append([i, m - 1])
  pacific[i][0] = True
  atlantic[i][m - 1] = True
 for i in range(m):
  pQueue.append([0, i])
  aQueue.append([n - 1, i])
  pacific[0][i] = True
  atlantic[n - 1][i] = True
 bfs(pQueue, pacific)  # 先查找能夠到達(dá)太平洋的坐標(biāo)
 bfs(aQueue, atlantic)  # 在查找能夠達(dá)到大西洋的坐標(biāo)

 for i in range(n):
  for j in range(m):
   # 哪些位置既可以到達(dá)太平洋也可以達(dá)到大西洋
   if pacific[i][j] and atlantic[i][j]:
 ans.append([i, j])
 return ans