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>

相關日誌