leetcode407. Trapping Rain Water II

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

 

Note:

Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

 

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length <= 2 || heightMap[0].length <= 2) {
            return 0;
        }
        int rowCount = heightMap.length;
        int columnCount = heightMap[0].length;
        boolean[][] visited = new boolean[rowCount][columnCount];
        PriorityQueue<Position> queue = new PriorityQueue<>();
        for (int i = 0 ; i < rowCount ; i++) {
            visited[i][0] = true;
            queue.offer(new Position(i, 0, heightMap[i][0]));
            visited[i][columnCount-1] = true;
            queue.offer(new Position(i, columnCount-1, heightMap[i][columnCount-1]));
        }

        for (int i = 1 ; i < columnCount ; i++) {
            visited[0][i] = true;
            queue.offer(new Position(0, i, heightMap[0][i]));
            visited[rowCount-1][i] = true;
            queue.offer(new Position(rowCount-1, i, heightMap[rowCount-1][i]));
        }

        int water = 0;
        int max = 0;
        while (!queue.isEmpty()) {
            Position position = queue.poll();
            if (position.value > max) {
                max = position.value;
            }else {
                water += max - position.value;
            }
            int rowIndex = position.rowIndex;
            int columnIndex = position.columnIndex;
            if (rowIndex > 0 && !visited[rowIndex-1][columnIndex]) {
                queue.offer(new Position(rowIndex-1, columnIndex, heightMap[rowIndex-1][columnIndex]));
                visited[rowIndex-1][columnIndex] = true;
            }
            if (rowIndex < rowCount-1 && !visited[rowIndex+1][columnIndex]) {
                queue.offer(new Position(rowIndex+1, columnIndex, heightMap[rowIndex+1][columnIndex]));
                visited[rowIndex+1][columnIndex] = true;
            }
            if (columnIndex > 0 && !visited[rowIndex][columnIndex-1]) {
                queue.offer(new Position(rowIndex, columnIndex-1, heightMap[rowIndex][columnIndex-1]));
                visited[rowIndex][columnIndex-1] = true;
            }
            if (columnIndex < columnCount - 1 && !visited[rowIndex][columnIndex+1]) {
                queue.offer(new Position(rowIndex, columnIndex+1, heightMap[rowIndex][columnIndex+1]));
                visited[rowIndex][columnIndex+1] = true;
            }
        }
        return water;
    }

    public static class Position implements Comparable<Position> {
        int rowIndex;
        int columnIndex;
        int value;

        Position(int rowIndex, int columnIndex, int value) {
            this.rowIndex = rowIndex;
            this.columnIndex = columnIndex;
            this.value = value;
        }

        @Override
        public int compareTo(Position o) {
            return this.value - o.value;
        }

    }