Pacific Atlantic Water Flow

class Solution {
		public List<List<Integer>> pacificAtlantic(int[][] matrix) {
				List<List<Integer>> result = new LinkedList<>();
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
		int m = matrix.length, n = matrix[0].length;
		boolean[][] pacific = new boolean[m][n];
		boolean[][] atlantic = new boolean[m][n];
		
		Queue<int[]> queP = new LinkedList<>();
		Queue<int[]> queA = new LinkedList<>();
		
		for (int i = 0; i < m; i++) {
			pacific[i][0] = true;
			atlantic[i][n - 1] = true;
			queP.offer(new int[]{i, 0});
			queA.offer(new int[]{i, n - 1});
		}
		for (int j = 0; j < n; j++) {
		pacific[0][j] = true;
		atlantic[m - 1][j] = true;
		queP.offer(new int[]{0, j});
		queA.offer(new int[]{m - 1, j});	
		}
		
		bfs(matrix, pacific, queP);
		bfs(matrix, atlantic, queA);
		
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; j++) {
				if (pacific[i][j] && atlantic[i][j]) {
						result.add(new ArrayList<>(Arrays.asList(i, j)));
				}	
			}	
		}
		return result;
		}
		private void bfs(int[][] matrix, boolean[][] water, Queue<int[]> queue) {
			int[] dx = {0, 0, 1, -1};
			int[] dy = {1, -1, 0, 0};
			
			while (!queue.isEmpty()) {
				int[] cell = queue.poll();
				int cx = cell[0];
				int cy = cell[1];
				for (int k = 0; k < 4; k++) {
					int nx = cx + dx[k];
					int ny = cy + dy[k];
					if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && matrix[nx][ny] >= matrix[cx][cy] && !water[nx][ny]) {
						water[nx][ny] = true;
						queue.offer(new int[]{nx, ny});
					}	
				}
			}	
		}
}

最后更新于

这有帮助吗?