Home Computer Science Java Algorithm

778 · Pacific Atlantic Water Flow - LintCode

# Description

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

1.The order of returned grid coordinates does not matter.
2.Both m and n are less than 150.

# Example

Example 1:

Input:
matrix = 
[[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]]
Output:
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation:
Pacific ~ ~ ~ ~ ~
      ~ 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 *
        * * * * * Atlantic

Example 2:

Input:
matrix =
[[1,2],
[4,3]]
Output:
[[0,1],[1,0],[1,1]]

# BFS Solution

一開始想錯了，想說只找到高的點，完全沒有考慮這個水的問題。傻傻的認為只要找最高的就行，是我天真了。從某 grid 開始找，找到最高也沒有用，因為不代表兩種水都可以流到那最高 grid。

於是有二個問題必須要解決：

  1. 從哪裡 開始找 target grid （找起點）
  2. 找交集

1. 從哪裡 開始找 target grid （找起點)
leetcode 有個題解的思路是 "水往高處流" （鍵盤在你手，水從哪裡流都行！） 左＋上的 pacific 的水 & 右＋下 atlantic 的水都會各自流到 "高處" (grid)；那低處的水呢？也一定能流到的，只是不一定會兩種水都一起流到而已。所以可以理解這是找 connected component 的一個問題。

而每個 matrix 邊都一定會流到各領域的水的，像 matrix[0][i] <- 第一行的 grid 都能流到 pacific 的水；於是第一行每一個 grid, 都是 pacific 的起點；可以把它放到只放 pacific 水的 queue 裡，然後進行 bfs 且判斷 target grid 是不是 ＝ 或> 其他 grid；對於 atlantic 水也一樣的做法。分開寫，用兩次 bfs。

2. 找交集
在 bfs 時，也把 pacific 訪問過的點都賦值為 true, atlantic 也一樣，最後只要跑一次 matrix 時判斷一下 grid 裡 pacific & atlantic 的水有沒有訪問過，都有的話代表它們有交集。

public class Solution {
    /**
     * @param matrix: the given matrix
     * @return: The list of grid coordinates
     */
   
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return res;
        }
        Queue<int[]> pQueue = new LinkedList<>();
        Queue<int[]> aQueue = new LinkedList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] reachP = new boolean[m][n];
        boolean[][] reachA = new boolean[m][n];
       
        for (int i = 0; i < m; i++) {
            //first col can reach Pacific water
            reachP[i][0] = true;            
            pQueue.offer(new int[]{i, 0});
            //last col can each atlantic water
            reachA[i][n - 1] = true;
            aQueue.offer(new int[]{i, n - 1});
        }
        for (int j = 0; j < n; j++) {
            // first row
            reachP[0][j] = true;
            pQueue.offer(new int[]{0, j});
            // last row
            reachA[m - 1][j] = true;
            aQueue.offer(new int[]{m - 1, j}); 
        }
        //find grid and mark it as true
        bfs(matrix, pQueue, reachP);
        bfs(matrix, aQueue, reachA);
		// find the grid that can flow pacific and alantic water
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (reachP[i][j] && reachA[i][j]) {
                    res.add(new ArrayList<>(Arrays.asList(i, j)));
                }
            }
        }
        return res;
    }
    private void bfs(int[][] matrix, Queue<int[]> queue, boolean[][] isVisited) {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        while (!queue.isEmpty()) {
            int[] coordinates = queue.poll();
            int x = coordinates[0], y = coordinates[1];
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX >= 0 && newX < matrix.length &&
                    newY >= 0 && newY < matrix[0].length && 
                    !isVisited[newX][newY] && matrix[newX][newY] >= matrix[x][y]) {
                        isVisited[newX][newY] = true;
                        queue.offer(new int[]{newX, newY});
                    }
            }
        }
    }
}