题目大意是在一个布满坑的地图上灌水，求最大储水量。
显然边界的坑是无法储水的，因此可以将边界的坑都加入一个保证坑的高度最小的优先队列（用二叉堆实现）。然后每次取出队列顶端的节点进行四个方向的灌水（如果高度比当前水位高度低则可增加储水量），将未曾加入队列的节点加入队列中继续这个过程直到队列为空即可。因为是从边界开始灌水，可以保证结果的正确性，同时显然可以确定每个坑只进出队列一次。故时间复杂度为O(nmlog(nm))。
7891534 IwfWcf 2227 Accepted 1288K 1719MS G++ 1631B 2010-11-18 18:22:05
帖子
0 评论:
发表评论