集訓(xùn)隊(duì)作業(yè)9915water解題報(bào)告

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

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

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

4、被標(biāo)號(hào)一次，在格子被標(biāo)號(hào)前只進(jìn)行一次寬度優(yōu)先搜索，而格子被標(biāo)號(hào)后就不再對(duì)它進(jìn)行任何操作了。故對(duì)每個(gè)格子的運(yùn)算量為 O（1）。因此算法的時(shí)間復(fù)雜度為O(n*m)。此算法對(duì)于所有測(cè)試數(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