Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean. Note: The order of returned grid coordinates does not matter. Both m and n are less than 150.

BFS

Time Complexity

思路

Add all boundary of Pacific ocean into queue. Do bfs and then reuse the same queue, if this point hasn't been visited and the value is bigger or equal to the current point value, then put it into queue and make it visited. Put all Atlantic ocean boundary into queue do the same bfs. We can't add one point to the queue twice, it will cause duplicate. If the point can be touched from Pacific ocean, add it into pac, if the point can be touched from Atlantic ocean, add it into alt. If one point is both in pac and alt, add it to res.

代码

public List
    
      pacificAtlantic(int[][] matrix) {    List
     
       res = new ArrayList
      
       ();    if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return res;    int rows = matrix.length, cols = matrix[0].length;    int[][] directions = new int[][]{
   {-1, 0},{1, 0},{0, -1},{0,1}};    boolean[][] pac = new boolean[rows][cols];    boolean[][] alt = new boolean[rows][cols];    Queue
       
         queue = new LinkedList
        
         ();    //add Pacific on left     for(int i = 0; i < rows; i++){        queue.offer(new int[]{i,0});        pac[i][0] = true;    }    //add Pacific on top    for(int j = 1; j < cols; j++){        queue.offer(new int[]{0,j});        pac[0][j] = true;    }    bfs(matrix, rows, cols, queue, pac, alt, directions, res);    //add Atlantic on bottom    for(int j = 0; j < cols - 1; j++){        queue.offer(new int[]{rows - 1, j});        alt[rows - 1][j] = true;    }    //add Atlantic on right    for(int i = 0; i < rows; i++){        queue.offer(new int[]{i, cols - 1});        alt[i][cols - 1] = true;     }    bfs(matrix, rows, cols, queue, alt, pac, directions, res);    return res;}private void bfs(int[][] matrix, int rows, int cols, Queue
         
           queue, boolean[][] self, boolean[][] others, int[][] directions, List
          
            res){ while(!queue.isEmpty()){ int[] cur = queue.poll(); if(others[cur[0]][cur[1]]) res.add(new int[]{cur[0],cur[1]}); for(int[] dir : directions){ int x = cur[0] + dir[0]; int y = cur[1] + dir[1]; if(x >= 0 && x < rows && y >= 0 && y < cols && self[x][y] == false && matrix[x][y] >= matrix[cur[0]][cur[1]]){ self[x][y] = true; queue.offer(new int[]{x,y}); } } }}