优先队列
注意到边界上的格子一定不能存水，否则会流到外面去。现在考虑与边界相邻的格子。注满水后，对于某个与边界相邻的格子来水，它的积水状态只与它自己的恶高度和相邻边界格子的最低高度有关。这样，我们可以取边界格子中高度最低的格子，然后来得到与之相邻的内部格子的水位。假设边界格子中高度最低的为格子(x,y)，那么对于(x,y)的任意一个相邻非边界格子(x’,y’)来说，只要
的积水，这时我们可以把
累加到答案中去，然后把
赋为
并把(x’,y’)看作边界格子。如果
，我们可以直接把(x’,y’)看作边界格子。当处理完所有(x,y)的相邻非边界格子后，把(x,y)从边界格子中删去。重复这个过程，直至边界格子集合为空为止。显然，用一个小根堆来维护边界格子集合是在适合不过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <iostream> using namespace std; const int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; bool u[111][111]; int ans,heapsize,h[111][111]; struct node { int x,y,v; } heap[11111]; void insert(int x,int y,int v) { node key={x,y,v}; int p=++heapsize; while(p>1&&heap[p>>1].v>v) { heap[p]=heap[p>>1]; p>>=1; } heap[p]=key; } void deleteMin() { int p=1; while((p<<1)<heapsize) { int i=p<<1; if(i+1<heapsize&&heap[i+1].v<heap[i].v) ++i; if(heap[i].v<heap[heapsize].v) { heap[p]=heap[i]; p=i; } else break; } heap[p]=heap[heapsize--]; } int main() { freopen("wod.in","r",stdin); freopen("wod.out","w",stdout); int r,c; scanf("%d%d",&r,&c); for(int i=0;i<r;++i) for(int j=0;j<c;++j) scanf("%d",&h[i][j]); for(int i=0;i<c;++i) { u[0][i]=u[r-1][i]=true; insert(0,i,h[0][i]); insert(r-1,i,h[r-1][i]); } for(int i=1;i+1<r;++i) { u[i][0]=u[i][c-1]=true; insert(i,0,h[i][0]); insert(i,c-1,h[i][c-1]); } while(heapsize) { int x=heap[1].x,y=heap[1].y; deleteMin(); for(int i=0;i<4;++i) { int tx=x+dx[i],ty=y+dy[i]; if(tx>-1&&tx<r&&ty>-1&&ty<c&&!u[tx][ty]) { u[tx][ty]=true; if(h[tx][ty]<h[x][y]) { ans+=h[x][y]-h[tx][ty]; h[tx][ty]=h[x][y]; } insert(tx,ty,h[tx][ty]); } } } printf("%d\n",ans); return 0; } |