Beyond the Void
BYVoid
POI 1999 积水 Water

根据木桶原理,水位的高低取决于最低的边界。我们可以从最低的边界入手,向内灌水,使水面于边界齐平。如果灌到了新的边界,而且不低于最低的边界,则这个点一定是不能被灌水的。

每次取边界最小值向内灌水,于是可以用一个最小堆来维护高度。

算法流程如下:

  1. 把所有的边界上的点加入堆,且标记为已使用过。
  2. 取出高度最小的点(x,y),枚举与(x,y)相邻的未使用过的点(x',y'),从(x',y')开始Floodfill,边界高度h=(x,y)的高度。
  3. 重复第二步,直到堆为空。
  • Floodfill(x,y)
  1. 标记(x,y)为已使用过。
  2. 如果(x,y)的高度>=h,则该点不能积水,加入堆并返回。
  3. 否则(x,y)的点的积水量为h-(x,y)的高度。
  4. 枚举与(x,y)相邻的未使用过的点(x',y'),Floodfill(x',y')。
/* 
 * Problem: POI1999 wod
 * Author: Guo Jiabao
 * Time: 2008.12.16 21:44:50
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=101;
const int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};

struct point
{
	int x,y;
};

int N,M,All;
int Alt[MAX][MAX];
bool vid[MAX][MAX];
int heap_size;
point Heap[MAX*MAX];

void heap_ins(int x,int y)
{
	int i;
	for (i=++heap_size;Alt[x][y]<Alt[Heap[i/2].x][Heap[i/2].y];i=i/2)
		Heap[i]=Heap[i/2];
	Heap[i].x=x; Heap[i].y=y;
}

point heap_delmin()
{
	point R=Heap[1],M=Heap[heap_size--];
	int i,c;
	for (i=1;i*2<=heap_size;i=c)
	{
		c=i*2;
		if (c!=heap_size && Alt[Heap[c+1].x][Heap[c+1].y]<Alt[Heap[c].x][Heap[c].y])
			c++;
		if (Alt[M.x][M.y] > Alt[Heap[c].x][Heap[c].y])
			Heap[i]=Heap[c];
		else
			break;
	}
	Heap[i]=M;
	return R;
}

void init()
{
	freopen("wod.in","r",stdin);
	freopen("wod.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (int i=1;i<=N;i++)
		for (int j=1;j<=M;j++)
			scanf("%d",&Alt[i][j]);
	Alt[0][0]=-0x7FFFFFFF;
	Heap[heap_size=0].x=Heap[0].y=0;
}

inline bool inrange(point A)
{
	return A.x>=1 && A.x<=N && A.y>=1 && A.y<=M;
}

void floodfill(point A,int h)
{
	point B;
	vid[A.x][A.y]=true;
	if (Alt[A.x][A.y]>=h)
		heap_ins(A.x,A.y);
	else
	{
		All+=h-Alt[A.x][A.y];
		for (int i=0;i<4;i++)
		{
			B.x=A.x+dx[i]; B.y=A.y+dy[i];
			if (inrange(B) && !vid[B.x][B.y])
				floodfill(B,h);
		}
	}
}

void solve()
{
	int i,j;
	point A,B;
	for (i=1;i<=N;i++)
	{
		heap_ins(i,1);
		heap_ins(i,M);
		vid[i][1]=vid[i][M]=true;
	}
	for (i=2;i<=M-1;i++)
	{
		heap_ins(1,i);
		heap_ins(N,i);
		vid[1][i]=vid[N][i]=true;
	}
	while (heap_size)
	{
		A=heap_delmin();
		for (i=0;i<4;i++)
		{
			B.x=A.x+dx[i]; B.y=A.y+dy[i];
			if (inrange(B) && !vid[B.x][B.y])
				floodfill(B,Alt[A.x][A.y]);
		}
	}
}

int main()
{
	init();
	solve();
	printf("%d",All);
	return 0;
}
<h2><span class="mw-headline">积水 </span></h2>

问题描述

有这样一块土地,它可以被划分N*M个正方形小块,每块面积是一平方英寸,第i行第j列的小块可以表示成P(i,j)。这块土地高低不平,每一小块地P(i,j)都有自己的高度H(i,j)(单位是英寸)。

一场倾盆大雨后,由于这块地地势高低不同,许多低洼地方都积存了不少降水。假如你已经知道这块土地的详细信息,你能求出它最多能积存多少立方英寸的降水么?

输入格式

输入文件的第一行是两个正整数n和m,1&lt;=n&lt;=100,1&lt;=m&lt;=100,表示土地的尺寸。下面n行,每行m个整数(1..10000);第j行第i个数表示第j行第i列立方体的高。

输出格式

输出文件只有一个数,表示在这个建筑上可以聚合的积水的最大值

输入输出样例

输入
<pre>3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1</pre>
输出
<pre>5</pre>
下图是其方案:

<a class="image" title="Image:Wod.png" href="http://www.ruvtex.cn/wiki/Image:Wod.png"><img src="http://www.ruvtex.cn/mw/images/7/73/Wod.png" alt="Image:Wod.png" width="193" height="110" /></a>

上次修改时间 2017-05-22

相关日志