Given a non-negative integer 2D array representing the heights of bars in a matrix. Suppose each bar has length and width of 1. Find the largest amount of water that can be trapped in the matrix. The water can flow into a neighboring bar if the neighboring bar's height is smaller than the water's height. Each bar has 4 neighboring bars to the left, right, up and down side.

Assumptions

• The given matrix is not null and has size of M * N, where M > 0 and N > 0, all the values are non-negative integers in the matrix.

Examples

{ { 2, 3, 4, 2 },

{ 3,1, 2,3 },

{ 4, 3, 5, 4 } }

the amount of water can be trapped is 3,

at position (1, 1) there is 2 units of water trapped,

at position (1, 2) there is 1 unit of water trapped.

Solution: 从外到内，先把边界加入pq，每次弹出，看周围4个点，如果高度低于cur.height，ans += cur.height - matrix[x][y]，加入pq的是cur.height(柱+水的高度)，否则加入matrix[x][y]

  class Node {
    int x, y, val;
    public Node(int i, int j, int k) {
      x = i;
      y = j;
      val = k;
    }
  }
  public int maxTrapped(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    if (m < 3 || n < 3) {
      return 0;
    }
    PriorityQueue<Node> pq = new PriorityQueue<>(1, new Comparator<Node>() {
      public int compare(Node a, Node b) {
        return a.val - b.val;
      }
    });
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < n; i++) {
      pq.offer(new Node(0, i, matrix[0][i]));
      pq.offer(new Node(m - 1, i, matrix[m - 1][i]));
      visited[0][i] = true;
      visited[m - 1][i] = true;
    }
    for (int i = 1; i < m; i++) {
      pq.offer(new Node(i, 0, matrix[i][0]));
      pq.offer(new Node(i, n - 1, matrix[i][n - 1]));
      visited[i][0] = true;
      visited[i][n - 1] = true;
    }
    int ans = 0;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    while (!pq.isEmpty()) {
      Node cur = pq.poll();
      for (int i = 0; i < 4; i++) {
        int x = cur.x + dx[i], y = cur.y + dy[i];
        if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
          if (matrix[x][y] < cur.val) {
            ans += cur.val - matrix[x][y];
            pq.offer(new Node(x, y, cur.val));
          } else {
            pq.offer(new Node(x, y, matrix[x][y]));
          }
          visited[x][y] = true;
        }
      }
    }
    return ans;
  }