A good problem.
Confused this one with DP. This one is a DFS problem.
First, though of traversing from each point and see if hits both pacific and altlantic boundary. Did not pass the tests. Got mistakes and TLE.
Then, though of traversing from ocean and see which points can be visited. Directly scanned from boundary to all other point by checking it upper and left / lower and right neighbors (a DP thought). But it is wrong. Consider this case:
5 5 1
3 4 2
5 3 3
The red 3 can reach pacific only through 3->3->2->1. If we only check upper and left neighbor, we won’t find this path and decide it cannot reach pacific.
The solution is simply change the algorithm one step further: scan from the ocean, and do DFS for each starting point:
// use two boolean matrices to store if any point can be visited starting from the ocean
boolean[][] pacific = new boolean[row][col];
boolean[][] atlantic = new boolean[row][col];
for (int i = 0; i < row; i++) {
dfs(matrix, i, 0, pacific); // search starting from pacific
dfs(matrix, i, col-1, atlantic); // search starting from atlantic
}
for (int j = 0; j < col; j++) {
dfs(matrix, 0, j, pacific); // same for the other boundary for pacific
dfs(matrix, row-1, j, atlantic); // the other boundary for atlantic
}
// when done searching, collect the point if it was visited by both the pacific and atlantic scan
The DFS function:
private void dfs(int[][] matrix, int i, int j, boolean[][] visited) {
if (visited[i][j]) return; // this is the point to avoid stack overflow, once visited, no need to check again
int row = matrix.length;
int col = matrix[0].length;
visited[i][j] = true;
for (int k = 0; k < 4; k++) {
// everything inside the loop are pretty standard
int ii = i+dx[k];
int jj = j+dy[k];
if (ii >= 0 && ii < row && jj >= 0 && jj < col && matrix[ii][jj] >= matrix[i][j]) {
dfs(matrix, ii, jj, visited);
}
}
}
Advertisements
