Comment on page

417.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];
for (int i = 0; i < n; i++) {
pacific[i][0] = true;
atlantic[i][m-1] = true;
}
for (int i = 0; i < m; 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();
}
}
}
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]) {
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();
}
}
}
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);
}
}
}