The Wedding Juicer
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 2803 | Accepted: 1225 |
Description
Farmer John's cows have taken a side job designing interesting punch-bowl designs. The designs are created as follows:
The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don't matter!
FJ's cows can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0.
- * A flat board of size W cm x H cm is procured (3 <= W <= 300, 3 <= H <= 300)
- * On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm block is placed. This block has some integer height B (1 <= B <= 1,000,000,000)
The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don't matter!
FJ's cows can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0.
Input
* Line 1: Two space-separated integers, W and H
* Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on.
* Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on.
Output
* Line 1: A single integer that is the number of cc's the described bowl will hold.
Sample Input
4 5 5 8 7 7 5 2 1 5 7 1 7 1 8 9 6 9 9 8 9 9
Sample Output
12
Hint
OUTPUT DETAILS:
Fill-up the two squares of height 1 to height 5, for 4 cc for each square. Fill the square of height 2 to height 5, for 3 cc of joice. Fill the square of height 6 to height 7 for 1 cc of juice. 2*4 + 3 + 1 = 12.
Fill-up the two squares of height 1 to height 5, for 4 cc for each square. Fill the square of height 2 to height 5, for 3 cc of joice. Fill the square of height 6 to height 7 for 1 cc of juice. 2*4 + 3 + 1 = 12.
Source
这是上届的省赛题，当时不会做，今天无意中看见一个课件上讲解了这题的思路，顿时明白了，还是刷了一下午，终于AC了，由此得出结论：菜鸟依旧是菜鸟。哎！！！
PPT上给的思路：
由外而内计算。每次选取外围的格子中积水高度最低的一个格子x，考虑它周围所有在网格内部的格子y
想象不断的往x和y里注水，但是x的积水高度固定（想象该高度处有一个小孔），因此
如果y的原始高度不小于x的积水高度，那么它的积水高度就是它的原始高度
如果y的原始高度小于x的积水高度，那么它的积水高度就等于x的积水高度
每次用堆取出x进行计算，O(mnlogmn)。
想象不断的往x和y里注水，但是x的积水高度固定（想象该高度处有一个小孔），因此
如果y的原始高度不小于x的积水高度，那么它的积水高度就是它的原始高度
如果y的原始高度小于x的积水高度，那么它的积水高度就等于x的积水高度
每次用堆取出x进行计算，O(mnlogmn)。
1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 5 using namespace std; 6 7 //优先队列默认是从大到小排列的，若要实现逆序，需要重载小于运算符。 8 struct node 9 { 10 int x, y; // 坐标 11 int h; 12 bool operator < (const node& p) const 13 { 14 return h > p.h; 15 } 16 }; 17 int map[305][305]; 18 bool vis[305][305]; 19 int dir[4][2] = {-1,0,0,1,1,0,0,-1}; 20 int col, row; 21 priority_queue<node> q; 22 23 24 void init() 25 { 26 for(int i = 1; i <= row; ++i) 27 for(int j = 1; j <= col; ++j) 28 { 29 vis[i][j] = false; 30 scanf("%d", &map[i][j]); 31 } 32 node t; 33 for(int i = 1; i <= row; ++i) 34 { 35 t.x = i; 36 t.y = 1; 37 t.h = map[i][1]; 38 q.push(t); 39 vis[i][1] = true; 40 41 t.x = i; 42 t.y = col; 43 t.h = map[i][col]; 44 q.push(t); 45 vis[i][col] = true; 46 } 47 for(int j = 2; j < col; ++j) 48 { 49 t.x = 1; 50 t.y = j; 51 t.h = map[1][j]; 52 q.push(t); 53 vis[1][j] = true; 54 55 t.x = row; 56 t.y = j; 57 t.h = map[row][j]; 58 q.push(t); 59 vis[row][j] = true; 60 } 61 } 62 63 long long BFS() 64 { 65 long long ans = 0; 66 int i, j; 67 node t1, t2; 68 while(!q.empty()) 69 { 70 t1 = q.top(); 71 q.pop(); 72 for(int k = 0; k < 4; ++k) 73 { 74 i = t1.x + dir[k][0]; 75 j = t1.y + dir[k][1]; 76 if(i > 0 && i <= row && j > 0 && j <= col && !vis[i][j]) 77 { 78 if(map[i][j] < t1.h) 79 { 80 ans += t1.h - map[i][j]; 81 t2.x = i; 82 t2.y = j; 83 t2.h = t1.h; 84 } 85 else 86 { 87 t2.x = i; 88 t2.y = j; 89 t2.h = map[i][j]; 90 } 91 vis[i][j] = true; 92 q.push(t2); 93 } 94 } 95 } 96 return ans; 97 } 98 99 int main() 100 { 101 while(~scanf("%d%d", &col, &row)) 102 { 103 init(); 104 printf("%lld\n", BFS()); 105 } 106 return 0; 107 }