417.Pacific-Atlantic-Water-Flow

417. Pacific Atlantic Water Flow

题目地址

https://leetcode.com/problems/pacific-atlantic-water-flow/

题目描述

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Example 1:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:
Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Note:
1 <= matrix.length <= 300
1 <= matrix[0].length <= 300
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8

代码

Approach #1 BFS

Time: O(NM) && Space: O(NM)

class Solution {
    int[][] dirs = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> ans = new ArrayList();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];

        Queue<int[]> pQueue = new LinkedList();
        Queue<int[]> aQueue = new LinkedList();

        for (int i = 0; i < n; i++) {
            pQueue.add(new int[]{i, 0});
            aQueue.add(new int[]{i, m-1});
            pacific[i][0] = true;
            atlantic[i][m-1] = true;
        }

        for (int i = 0; i < m; i++) {
            pQueue.add(new int[]{0, i});
            aQueue.add(new int[]{n-1, i});
            pacific[0][i] = true;
            atlantic[n-1][i] = true;
        }

        bfs(matrix, pQueue, pacific);
        bfs(matrix, aQueue, atlantic);


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> pos = new ArrayList();
                    pos.add(i);
                    pos.add(j);
                    ans.add(pos);
                }
            }
        }

        return ans;
    }

    private void bfs(int[][] matrix,  Queue<int[]> queue, boolean[][] visited) {
        int n = matrix.length;
        int m = matrix[0].length;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir: dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];

                if (x < 0 || x >= n || y < 0 || y >= m || matrix[x][y] < matrix[cur[0]][cur[1]] ) {
                    continue;
                }

                if (!visited[x][y]) {
                    queue.add(new int[]{x, y});
                    visited[x][y] = true;
                }

            }
        }

    }
}

Approach #2 DFS

Time: O(NM) && Space: O(NM)

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> ans = new ArrayList();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }

        int n = matrix.length;
        int m = matrix[0].length;

        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];


        for (int i = 0; i < n; i++) {
            dfs(matrix, pacific, i, 0);
            dfs(matrix, atlantic, i, m - 1);
            pacific[i][0] = true;
            atlantic[i][m-1] = true;
        }

        for (int i = 0; i < m; i++) {
            dfs(matrix, pacific, 0, i);
            dfs(matrix, atlantic, n - 1, i);
            pacific[0][i] = true;
            atlantic[n-1][i] = true;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> loc = new ArrayList();
                    loc.add(i);
                    loc.add(j);
                    ans.add(loc);
                }
            }
        }

        return ans;
    }

    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private void dfs(int[][] matrix, boolean[][] visited, int x, int y) {
        int n = matrix.length;
        int m = matrix[0].length;
        for (int[] dir: dirs) {
            int r = x + dir[0];
            int c = y + dir[1];
            if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c] || matrix[x][y] > matrix[r][c]) {
                continue;
            }

            visited[r][c] = true;
            dfs(matrix, visited, r, c);
        }

    }


}