|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.PriorityQueue; |
| 4 | + |
| 5 | +/** |
| 6 | + * 407. Trapping Rain Water II |
| 7 | + * |
| 8 | + * 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. |
| 9 | +
|
| 10 | + Note: |
| 11 | + Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000. |
| 12 | +
|
| 13 | + Example: |
| 14 | +
|
| 15 | + Given the following 3x6 height map: |
| 16 | + [ |
| 17 | + [1,4,3,1,3,2], |
| 18 | + [3,2,1,3,2,4], |
| 19 | + [2,3,3,2,3,1] |
| 20 | + ] |
| 21 | +
|
| 22 | + Return 4. |
| 23 | +
|
| 24 | + 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. |
| 25 | +
|
| 26 | + After the rain, water are trapped between the blocks. The total volume of water trapped is 4. |
| 27 | +
|
| 28 | + */ |
| 29 | +publicclass_407 { |
| 30 | +/**Reference: https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue*/ |
| 31 | +publicclassCell { |
| 32 | +introw; |
| 33 | +intcol; |
| 34 | +intheight; |
| 35 | + |
| 36 | +publicCell(introw,intcol,intheight) { |
| 37 | +this.row =row; |
| 38 | +this.col =col; |
| 39 | +this.height =height; |
| 40 | + } |
| 41 | + } |
| 42 | + |
| 43 | +publicinttrapRainWater(int[][]heights) { |
| 44 | +if (heights ==null ||heights.length ==0 ||heights[0].length ==0) |
| 45 | +return0; |
| 46 | + |
| 47 | +PriorityQueue<Cell>queue =newPriorityQueue<>(1, (a,b) ->a.height -b.height); |
| 48 | + |
| 49 | +intm =heights.length; |
| 50 | +intn =heights[0].length; |
| 51 | +boolean[][]visited =newboolean[m][n]; |
| 52 | + |
| 53 | +// Initially, add all the Cells which are on borders to the queue. |
| 54 | +for (inti =0;i <m;i++) { |
| 55 | +visited[i][0] =true; |
| 56 | +visited[i][n -1] =true; |
| 57 | +queue.offer(newCell(i,0,heights[i][0])); |
| 58 | +queue.offer(newCell(i,n -1,heights[i][n -1])); |
| 59 | + } |
| 60 | + |
| 61 | +for (inti =0;i <n;i++) { |
| 62 | +visited[0][i] =true; |
| 63 | +visited[m -1][i] =true; |
| 64 | +queue.offer(newCell(0,i,heights[0][i])); |
| 65 | +queue.offer(newCell(m -1,i,heights[m -1][i])); |
| 66 | + } |
| 67 | + |
| 68 | +// from the borders, pick the shortest cell visited and check its neighbors: |
| 69 | +// if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped |
| 70 | +// add all its neighbors to the queue. |
| 71 | +int[][]dirs =newint[][]{{-1,0}, {1,0}, {0, -1}, {0,1}}; |
| 72 | +intres =0; |
| 73 | +while (!queue.isEmpty()) { |
| 74 | +Cellcell =queue.poll(); |
| 75 | +for (int[]dir :dirs) { |
| 76 | +introw =cell.row +dir[0]; |
| 77 | +intcol =cell.col +dir[1]; |
| 78 | +if (row >=0 &&row <m &&col >=0 &&col <n && !visited[row][col]) { |
| 79 | +visited[row][col] =true; |
| 80 | +res +=Math.max(0,cell.height -heights[row][col]); |
| 81 | +queue.offer(newCell(row,col,Math.max(heights[row][col],cell.height))); |
| 82 | + } |
| 83 | + } |
| 84 | + } |
| 85 | + |
| 86 | +returnres; |
| 87 | + } |
| 88 | +} |