1. 題目
4.water pail
題目描述：
Zz同學家裡有一個奇怪的水桶，這個水桶不是圓柱型的，它的底面是一個長方形，合格長方形是由n*m個格子構成的，這個水桶更奇怪的地方是水桶内的每個格子的高度都是不同的。既然是水桶，那麼Zz同學請你求出這個水桶最多能裝多少體積的水
輸入：
第一行兩個正整數n,m (0<n,m<=300)
接下來是一個n*m的矩形，I行j列的數字代表水桶内該格子的高度h（0<=h<=1 000 000 000）
輸出：
最多裝水的體積
樣例：
輸入：
4 5 5 8 7 7 5 2 1 5 7 1 7 1 8 9 6 9 9 8 9 9 輸出： 12 資料範圍：
對于30%的資料
1<=n,m<=10
對于100%的資料
1<=n<=500
1<=m<=500
2. 題目實質
這個，就是灌水。
難道這就是 Floodfill 的原型？
3. 算法
floodfill + 隊列 + 堆優化
首先，在邊緣的一圈找到一個最小的點，然後從這個點（先從小到大選擇邊緣上的點，然後再往裡選，這個用隊列來維護）開始 floodfill ，擴充那些比他小的點（将他們賦為這個點的值，再将這個點賦為 maxlongint ，這樣能夠保證以後不會再一次擴充到他），然後将擴充的所有點入隊（因為不能再擴充了，隊列存的是不能再擴充的點），然後每次找隊列中最小的點（維護隊列的隊首元素是最小的，但不能用單調隊列的方法維護，那樣會改變元素個數，就正常的維護）進行擴充，依此類推。
注意這個資料比較變态，是以維護隊列時要用到堆。
4. 注意事項
要用堆優化。
5. 程式代碼
dsqwee (pascal)
program dsqwwe;
const
dx:array[1..4] of longint=(0,0,1,-1);
dy:array[1..4] of longint=(1,-1,0,0);
type
tt=record
x,y,t:longint;
end;
var
d:array[1..250000] of tt;
v:array[0..505,0..505] of boolean;
a:array[0..505,0..505] of longint;
n,m,i,j,tot,open,x,y,xx,yy,t:longint;
ans:int64;
procedure swap(x,y:longint);
var
t:tt;
begin
t:=d[x]; d[x]:=d[y]; d[y]:=t;
end;
procedure up(i:longint);
var
j:longint;
begin
while i>1 do
begin
j:=i div 2;
if d[i].t<d[j].t then swap(i,j) else break;
i:=j;
end;
end;
procedure down(i:longint);
var
j:longint;
begin
while i<=tot div 2 do
begin
j:=i*2;
if (d[j].t>d[j+1].t) and (j+1<=tot) then inc(j);
if d[i].t>d[j].t then swap(i,j) else break;
i:=j;
end;
end;
begin
assign(input,'pail.in');reset(input);
assign(output,'pail.out');rewrite(output);
readln(m,n);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
for i:=1 to m do
begin
inc(tot);
v[1,i]:=true;
d[tot].t:=a[1,i];
d[tot].x:=1;
d[tot].y:=i;
up(tot);
inc(tot);
v[n,i]:=true;
d[tot].t:=a[n,i];
d[tot].x:=n;
d[tot].y:=i;
up(tot);
end;
for i:=2 to n-1 do
begin
inc(tot);
v[i,1]:=true;
d[tot].t:=a[i,1];
d[tot].x:=i;
d[tot].y:=1;
up(tot);
inc(tot);
v[i,m]:=true;
d[tot].t:=a[i,m];
d[tot].x:=i;
d[tot].y:=m;
up(tot);
end;
while tot<n*m do
begin
x:=d[1].x;
y:=d[1].y;
t:=d[1].t;
d[1].t:=maxlongint;
down(1);
for i:=1 to 4 do
begin
xx:=x+dx[i];
yy:=y+dy[i];
if (xx>0) and (xx<=n) and (yy>0) and (yy<=m) then
if not v[xx,yy] then
begin
inc(tot);
d[tot].x:=xx;
d[tot].y:=yy;
if t>a[xx,yy] then begin
inc(ans,t-a[xx,yy]);
d[tot].t:=t;
end
else d[tot].t:=a[xx,yy];
up(tot);
v[xx,yy]:=true;
end;
end;
end;
writeln(ans);
close(input);
close(output);
end.
轉載于:https://www.cnblogs.com/SueMiller/archive/2011/08/11/2135281.html