05 August 2008
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
/*
https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90733/Java-BFS-and-DFS-from-Ocean
http://blog.csdn.net/mebiuw/article/details/52766269
给定一个m*n的矩阵，矩阵的每一个元素代表一个大陆的一块区域的高度。矩阵的上边界和左边界外是Pacific，下边界和右边界是Atlantic。水向低处走，所以当前区域的高度高于或等于相邻区域时，水可以从当前区域流向相邻区域。本题要求的点是，从该点出发，既可以流到Pacific也可以流到Atlantic
*/
//BFS
int[][]dir = new int[][]{ {1,0},{-1,0},{0,1},{0,-1} };
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new LinkedList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return res;
}
int n = matrix.length, m = matrix[0].length;
//One visited map for each ocean
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++) {// Vertical border
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++) {//Horizontal border
pQueue.offer(new int[]{0, i});
aQueue.offer(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]) {
res.add(new int[]{i, j});
}
}
}
return res;
}
public void bfs(int[][] matrix, Queue<int[]> queue, boolean[][] visited) {
int n = matrix.length, m = matrix[0].length;
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d: dir) {
int x = cur[0] + d[0];
int y = cur[1] + d[1];
if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]) {
continue;
}
visited[x][y] = true;
queue.offer(new int[]{x, y});
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 写着广度优先遍历，实际上由是一道深度搜索的题目
//大致思路就是找到太平洋所能到达的地方记录下来，然后找到大西洋所能到达的点记录下来，然后找到重叠的点,且值都为1
//的点就是所求，看了一个评论区大佬的思路就是设置一个数组将太平洋能到达的地点加一，然后将大西洋能到达的地点在加一
//最后值为2的点就是所求,忽然想了想这种思路可能不太好，因为深度优先遍历过程中可能会重复遍历到某个点
// 还是设置两个数组的好
class Solution {
int min=Integer.MIN_VALUE;
// 创建一个二维数组记录海洋所能到达的点
int[][] preach;
int[][] areach;
// 创建一个集合保存结果
List<List<Integer>> list=new ArrayList <List<Integer>>();
public List<List<Integer>> pacificAtlantic(int[][] heights) {
// 分别创建两个数组记录两个海洋所能到达的陆地
preach=new int[heights.length][heights[0].length];
areach=new int[heights.length][heights[0].length];
//将太平洋边上的每个点都进行深搜
for(int i=0;i<heights[0].length;i++){
dfs(heights, preach,0,i, min);
}
for(int i=0;i<heights.length;i++){
dfs(heights, preach,i,0, min);
}
// 将大西洋边上的每个点都进行深搜
for(int i=0;i<heights[0].length;i++){
dfs(heights, areach,heights.length-1,i, min);
}
for(int i=0;i<heights.length;i++){
dfs(heights, areach,i,heights[0].length-1, min);
}
//创建一个集合保存坐标
List<Integer> temp;
//比较重复的点，且值为1的点，并将他们的坐标放进集合中去
for(int i=0;i<heights.length;i++){
for(int j=0;j<heights[0].length;j++){
if(preach[i][j]==1&&areach[i][j]==1){
temp=new ArrayList<Integer>();
temp.add(i);
temp.add(j);
list.add(temp);
}
}
}
return list;
}
// 创建一个深度优先搜索函数
public void dfs(int[][] heights, int[][] reach,int rstart,int cstart,int pre){
// 深度优先搜索的出口
// 当超出二维数组的范围时:rstart<0||cstart<0||rstart>=heights.length||cstart>=heights[0].length
// 当某个点的值必它本身要小的时候:heights[rstart][cstart]<pre
// 由或者该点已经被搜索过了 : reach[rstart][cstart]==1
if(rstart<0||cstart<0||rstart>=heights.length||cstart>=heights[0].length||heights[rstart][cstart]<pre||reach[rstart][cstart]==1){
return;
}
int temp=heights[rstart][cstart];
reach[rstart][cstart]=1;
// 想该点的四个方向进行搜索
dfs(heights, reach,rstart+1,cstart,temp);
dfs(heights, reach,rstart,cstart-1,temp);
dfs(heights, reach,rstart,cstart+1,temp);
dfs(heights, reach,rstart-1,cstart,temp);
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class pacificAtlantic {
private static int[][] dires = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
private int m, n;
private int[][] matrix;
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res = new ArrayList<>();
m = matrix.length;
if (m == 0)
return res;
n = matrix[0].length;
if (n == 0)
return res;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}
for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(canReachA[i][j] && canReachP[i][j]){
List<Integer> temp = new ArrayList<>();
temp.add(i);
temp.add(j);
res.add(temp);
}
}
}
return res;
}
/**
* 换一种思路，从边界往里面走，只能走到比自己更高或者等高的地方。边界能走到的地方，就是能流入对应海洋的地方。
*/
private void dfs(int x, int y, boolean[][] canReach) {
canReach[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + dires[i][0];
int newY = y + dires[i][1];
if (isIn(newX, newY) && matrix[x][y] <= matrix[newX][newY] && !canReach[newX][newY]) {
dfs(newX, newY, canReach);
}
}
}
private boolean isIn(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}