SHARE
TWEET

Untitled

a guest Sep 22nd, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     int m, n;
  3.     public List<List<Integer>> pacificAtlantic(int[][] matrix) {
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         if(matrix.length == 0 || matrix[0].length == 0) return res;
  6.         m = matrix.length;
  7.         n = matrix[0].length;
  8.        
  9.         boolean[][] pOcean = new boolean[m][n];
  10.         boolean[][] aOcean = new boolean[m][n];
  11.         Queue<int[]> pQueue = new LinkedList<>();
  12.         Queue<int[]> aQueue = new LinkedList<>();
  13.         for(int i = 0; i < m; i++){
  14.             pQueue.add(new int[]{i, 0});
  15.             aQueue.add(new int[]{i, n-1});
  16.             pOcean[i][0] = true;
  17.             aOcean[i][n-1] = true;
  18.         }
  19.         for(int i = 0; i < n; i++){
  20.             pQueue.add(new int[]{0, i});
  21.             aQueue.add(new int[]{m-1, i});
  22.             pOcean[0][i] = true;
  23.             aOcean[m-1][i] = true;
  24.         }
  25.         bfs(aQueue, matrix, aOcean);
  26.         bfs(pQueue, matrix, pOcean);
  27.        
  28.         for(int i = 0; i < m; i++){
  29.             for(int j = 0; j < n; j++){
  30.                 if(aOcean[i][j] && pOcean[i][j])    res.add(Arrays.asList(i, j));
  31.             }
  32.         }
  33.         return res;
  34.     }
  35.    
  36.     int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  37.     private void bfs(Queue<int[]> queue, int[][] matrix, boolean[][] visited){
  38.         while(!queue.isEmpty()){
  39.             int[] pos = queue.poll();
  40.             for(int[] d: dir){
  41.                 int x = pos[0] + d[0];
  42.                 int y = pos[1] + d[1];
  43.                 if(x < 0 || y < 0 || x >= m || y >= n || visited[x][y] || matrix[x][y] < matrix[pos[0]][pos[1]])    continue;
  44.                 visited[x][y] = true;
  45.                 queue.add(new int[]{x, y});
  46.             }
  47.         }
  48.     }
  49. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top