集訓(xùn)隊作業(yè)9915water解題報告

1、解題題意描述根據(jù)水的性質(zhì)，水總是望較低的方向流的，如果一個地區(qū)的積水能流到整個地區(qū)的邊緣，那么這個地區(qū)就不會積水了。同樣的，可積水地區(qū)積水的高度也是由這個性質(zhì)決定的。很自然的，每個格子積水的高度是有周圍的四個格子決定的。于是想到一個類似于松弛算法的想法：最開始時，每個格子積水的高度定為一個充分大的值，每次搜索所有的格子，將格子中積水的高度按照周圍格子的情況改變。這樣的過程一直持續(xù)到?jīng)]有需要改變的格子為止。這樣得到的就是每個格子中積水的最大值。程序編起來也非常簡單，但分析了算法的時就不得不放棄這法：算法的時間復(fù)雜度高達(dá) O（n2*m2）間復(fù)雜度后，算法分析來換一個角度問題，可積水地區(qū)一定是凹陷的

2、，也就是說它的周圍被一層較高的建筑包起來了。是不是可以求這樣的一個封閉的區(qū)域呢，然后再求積水的高度就可以簡單一些了。連通的積水格子看成一個大塊。每個積水塊都是由不積水的干地包圍起來的。當(dāng)然也可能出現(xiàn)一個積水塊被另一個包在的情況（如上圖所示）。首先考慮在最外層的積水塊 A。對于那些包圍 A 的干地，落在它們上面的雨水一定是流到地圖的邊緣了，否則它們也將積水。這樣可以簡單的利用寬度優(yōu)先搜索的方法將 A 的輪廓勾勒出來：從最邊緣的格子開始，分析每格干地，查看這個格子周圍的四格，如果有格子高于當(dāng)前格的高度，那么那個格子上的水也將流向地圖邊緣而成為干地。將那個格子加入到待分析的隊列中并將這個格子標(biāo)上已操

3、作標(biāo)記。寬度優(yōu)先搜索后，A 的輪廓就出來了。沿著 A 的輪廓順時101010101010101088888101081111118101081191181010811111181010888881010101010101010針走一圈后，就可以得到輪廓中的格子的最低高度，而這就是 A 中積水的高度。仍然用寬度優(yōu)先的算法，可以遍歷 A 中的格子。統(tǒng)計了 A 中格子內(nèi)的積水量后，將每個格子的高度提高到與水面相平。如上面的例子里，在對高度為 8 的格子注水以后，地圖變成了下面的情況。在這張圖里可以清楚的看到原先的積水區(qū)變成了干地。這樣就能對原先處于的積水區(qū)進(jìn)行操作了。算法效率在剛才的算法里每個格子僅

4、被標(biāo)號一次，在格子被標(biāo)號前只進(jìn)行一次寬度優(yōu)先搜索，而格子被標(biāo)號后就不再對它進(jìn)行任何操作了。故對每個格子的運算量為 O（1）。因此算法的時間復(fù)雜度為O(n*m)。此算法對于所有測試數(shù)據(jù)都能在 0.5s 內(nèi)出解。源程序constinf ouf maxnmove=wod.in;=wod.out;=10;:array1.4,1.2 ofeger=(-1,0),(1,0),(0,1),(0,-1);varn,m,i,j map findtot:eger;:array1.maxn,1.maxn of:array1.maxn,1.maxn of:long;eger;eger;function max(a,b

5、:eger):eger;1010101010101010101010101010101011111110101010119111010101011111110101010101010101010101010101010beginif ab then max:=a else max:=b;end;procedure work(sx,sy: varlistp,q,x,yeger);:array1.maxn*maxn,1.2 of:eger;eger;beginp:=1;q:=1;list1,1:=sx;list1,2:=sy;findsx,sy:=2; while p=q do beginfor

6、i:=1 to 4 do begin x:=listp,1+movei,1;y:=listp,2+movei,2;if (x0) and (y0)and (findx,y=0) and (mapx,y=maplistp,1,listp,2) then begin findx,y:=2;inc(q); listq,1:=x;listq,2:=y;end; end; inc(p);end;end;function get(i,j:eger):eger; vark,u,x,y beginu:=max;for k:=1 to 4 do begin x:=i+movek,1;y:=j+movek,2;:

7、eger;if (x0) and (y0)and (findx,y=2) and (mapx,yu) then u:=mapx,y;end;get:=u;end;function find_min(sx,sy:eger):eger;varlistp,q,x,y,min,k:array1.maxn*maxn,1.2 of:eger;eger;beginp:=1;q:=1;list1,1:=sx;list1,2:=sy;findsx,sy:=1;min:=get(sx,sy); while p=q do beginfor i:=1 to 4 do begin x:=listp,1+movei,1;

8、y:=listp,2+movei,2;if (x0) and (y0) and (findx,y=0) then begin k:=get(x,y);if kmhen min:=k;findx,y:=1; inc(q); listq,1:=x;listq,2:=y;end;end;inc(p);end;find_min:=min;end;procedure sum(sx,sy,k: varlistp,q,x,yeger);:array1.maxn*maxn,1.2 of:eger;eger;beginp:=1;q:=1;list1,1:=sx;list1,2:=sy;findsx,sy:=2;

9、 tot:=tot+k-mapsx,sy;while p=q do beginfor i:=1 to 4 do begin x:=listp,1+movei,1;y:=listp,2+movei,2;if (x0) and (y0) and (findx,y=1) then begin findx,y:=2;tot:=tot+max(0,k-mapx,y); inc(q);listq,1:=x;listq,2:=y;end; end; inc(p);end;end;procedure solve; vari,j,k:eger;beginfillchar(find,sizeof(find),0); for i:=1 to n do beginwork(i,1);work(i,m);end;for i:=1 to m do begin work(1,i);work(n,i);end; tot:=0;for i:=1 to n do for j:=1 to m k:=find_min(i,j); sum(i,j,k);end;wrin(tot);end;f findi,j=0 then beginbeginassign(input