[LC 417] Pacific Atlantic Water Flow

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s