正常做的，用了645MS。。感觉DFS的时候剪枝有问题。。
为了剪枝可能需要标记一个点的4种情况：
1：滨临大西洋，所有太平洋来的点可以通过；
2：濒临太平洋，所有大西洋来的点可以通过；
3：都不濒临，直接RETURN；
4：都濒临，通过；
这样的话用DP记录情况，应该能做。。
看了答案发现一开始思路就错了。。但是这个645MS居然能AC。。。。。。。。。。 正确思路看第二段代码吧。
public class Solution
{
public List<int[]> pacificAtlantic(int[][] matrix)
{
List<int[]> res = new ArrayList<int[]>();
if(matrix.length == 0) return res;
boolean[][] dp = new boolean[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length;i++)
for(int j = 0; j < matrix[0].length;j++)
{
boolean[] a = new boolean[2];
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
helper(matrix,dp,visited,i,j,a);
if(a[0] && a[1])
{
int[] temp = new int[2];
temp[0] = i;
temp[1] = j;
dp[i][j] = true;
res.add(temp);
}
}
return res;
}
public void helper(int[][] map,boolean[][] dp,boolean[][] visited, int m,int n,boolean[] a)
{
int val = map[m][n];
if(dp[m][n])
{
a[0]=true;
a[1]=true;
return;
}
if(m == 0) a[0] = true;
else if(map[m-1][n] <= val && !visited[m-1][n])
{
visited[m-1][n] = true;
helper(map,dp,visited,m-1,n,a);
}
if(a[0]&&a[1]) return;
if(n == 0) a[0] = true;
else if(map[m][n-1] <= val && !visited[m][n-1])
{
visited[m][n-1] = true;
helper(map,dp,visited,m,n-1,a);
}
if(a[0]&&a[1]) return;
if(m == map.length-1) a[1] = true;
else if(map[m+1][n] <= val && !visited[m+1][n])
{
visited[m+1][n] = true;
helper(map,dp,visited,m+1,n,a);
}
if(a[0]&&a[1]) return;
if(n == map[0].length-1) a[1] = true;
else if(map[m][n+1] <= val && !visited[m][n+1])
{
visited[m][n+1] = true;
helper(map,dp,visited,m,n+1,a);
}
return;
}
}
看了讨论，发现自己好蠢，这个水平别去面试了，回家吃屎行了。
不一定需要遍历整个图。以滨临大西洋的做DFS，再以滨临太平洋的做DFS，合集就是要求的点。
public class Solution
{
public List<int[]> pacificAtlantic(int[][] matrix)
{
List<int[]> res = new ArrayList<int[]>();
if(matrix.length == 0) return res;
int m = matrix.length;
int n = matrix[0].length;
boolean[][] p = new boolean[m][n];
boolean[][] a = new boolean[m][n];
boolean[][] visited = new boolean[m][n];
for(int i = 0; i < matrix.length;i++)
{
p[i][0] = true;
a[i][n-1] = true;
visited = new boolean[m][n];
helper(matrix,p,i,0,visited);
visited = new boolean[m][n];
helper(matrix,a,i,n-1,visited);
}
for(int i = 0; i < matrix[0].length;i++)
{
p[0][i] = true;
a[m-1][i] = true;
visited = new boolean[m][n];
helper(matrix,p,0,i,visited);
visited = new boolean[m][n];
helper(matrix,a,m-1,i,visited);
}
for(int i = 0; i < m;i++)
for(int j = 0; j < n;j++)
if(a[i][j] == true && p[i][j] == true)
{
int[] temp = new int[2];
temp[0] = i;
temp[1] = j;
res.add(temp);
}
return res;
}
public void helper(int[][] matrix,boolean[][] map,int m, int n,boolean[][] visited)
{
if(visited[m][n]) return;
visited[m][n] = true;
map[m][n] = true;
int v = matrix[m][n];
if(m > 0 && matrix[m-1][n]>=v) helper(matrix,map,m-1,n,visited);
if(n > 0 && matrix[m][n-1]>=v) helper(matrix,map,m,n-1,visited);
if(m < map.length-1 && matrix[m+1][n] >= v) helper(matrix,map,m+1,n,visited);
if(n < map[0].length-1 && matrix[m][n+1] >= v) helper(matrix,map,m,n+1,visited);
}
}