1513 煩惱的設(shè)計師(來自SGOI)

1、【數(shù)據(jù)結(jié)構(gòu)hash表】煩惱的設(shè)計師（SGOI）Time Limit:10000MS Memory Limit:65536KTotal Submit:55 Accepted:18 Description 煩惱的設(shè)計師（來自SGOI） 春天到了，百花齊放，西湖公園里新設(shè)置了許多花壇，設(shè)計師想用不同的花擺出不同的圖案以吸引游人，于是設(shè)計了各種圖案并且在花圃中選好了要擺放的花。不幸的是負責(zé)搬運和擺放的工人因為臨時有事，只將花放到花架上就匆匆離開了，并沒有按照設(shè)計師原來的設(shè)計方案擺放，結(jié)果花壇雜亂不堪,設(shè)計師只好自己來調(diào)整花的位置。由于設(shè)計師通常從事腦力勞動，較少從事搬運和擺放花盆的體力工作，所以請你幫

2、忙找出一種移動方法使工作量最小。 不同種類的花有不同的類型編號，雖然地球上花的種類很多，但因為公園里的花不超過1,000,000種，所以花的類型編號不超過1,000,000。另一方面，出于美學(xué)考慮，一個花壇里擺放的不同種類的花不超過3種，且不同種類的花的數(shù)量不可太接近，對于任意兩種花，數(shù)量多的花的盆數(shù)至少是數(shù)量少的花的2倍。 花壇是正六邊形的，共擺放有19盆花，每盆花都放在一個轉(zhuǎn)盤上，轉(zhuǎn)動一盆花下面的轉(zhuǎn)盤，會使周圍的6盆花順時針或逆時針移動一個位置（但不可把花轉(zhuǎn)到花壇外），稱為一次操作。你的任務(wù)：用最少的操作使花壇由初始狀態(tài)轉(zhuǎn)化為符合設(shè)計圖紙的目標狀態(tài)。例如： 初始狀態(tài)目標狀態(tài)如圖，只需將處于

3、圓心位置的那盆花的轉(zhuǎn)盤順時針轉(zhuǎn)動一個位置，紅色的花就移動到了目標位置。 Input 輸入文件共11行，1至5行描述花壇的初始狀態(tài)，7至11行表示花盆應(yīng)擺放的位置。中間以空行分隔，5行數(shù)字分別表示花壇的5個行，其中第1、5兩行有3個整數(shù)，第2、4兩行有4個整數(shù)，第3行有5個整數(shù)，表示每一行的花的類型，不同的數(shù)代表不同種類的花。 Output 輸出文件，一行，包含一個整數(shù)，即最少的操作數(shù)，數(shù)據(jù)保證20步之內(nèi)有解。 Sample Input 1 1 11 2 1 11 1 1 1 11 1 1 11 1 11 1 11 1 1 11 1 2 1 11 1 1 11 1 1Sample Output

4、1Hint 題意描述: 給定兩個正6邊形的花壇，要求求出從第一個變化到第二個的最小操作次數(shù)以及操作方式。一次操作是：選定不在邊上的一盆花，將這盆花周圍的6盆花按照順時針或者逆時針的順序依次移動一個單位。限定一個花壇里擺放的不同種類的花不超過3種，對于任意兩種花，數(shù)量多的花的盆數(shù)至少是數(shù)量少的花的2倍 。（這是 SGOI-8 的一道題） 解題分析： 首先確定本題可以用廣度優(yōu)先搜索處理，然后來看問題的規(guī)模。正6邊形共有19個格子可以用來放花，而且根據(jù)最后一句限定條件，至多只能存在 C(2,19) * C(5,17) = 1058148 種狀態(tài)，用搜索完全可行。然而操作的時候，可以預(yù)料產(chǎn)生的重復(fù)節(jié)點

5、是相當多的，需要迅速判重才能在限定時間內(nèi)出解，因此想到了哈希表。那么這個哈希函數(shù)如何設(shè)計呢？注意到19個格子組成6邊形是有順序的，而且每一個格子只有3種可能情況，那么用3進制19位數(shù)最大 320-1=3486784400，注意，這個數(shù)值大于231，但小于232。于是我們將每一個狀態(tài)與一個整數(shù)對應(yīng)起來，使用除余法就可以了。 Source program flowers; const size=1058148; base=262143; circle:array1.7,1.6 of integer= (1,2,6,10,9,4), (2,3,7,11,10,5), (4,5,10,14,13,8)

6、, (5,6,11,15,14,9), (6,7,12,16,15,10), (9,10,15,18,17,13), (10,11,16,19,18,14) ); var i,j,k,l,ps,r,step:longint; hash:array0.base of longint; next,q:array0.size of longint; d:array0.7 of longint; bit,s,t:array1.19 of longint; start,target:longint; function change(a,b:longint; plus:integer):longint;

7、var i:integer; begin for i:=1 to 6 do di:=(a div bitcircleb,i) mod 3; d7:=d1; d0:=d6; for i:=1 to 6 do a:=a+(di+plus-di)*bitcircleb,i; change:=a; end; procedure insert(x:longint); var i:longint; begin if x=target then begin writeln(step); halt; end; i:=x mod base; if hashi=0 then begin inc(ps); qps:

8、=x; hashi:=ps; end else begin i:=hashi; while nexti0 do begin if qi=x then exit; i:=nexti; end; if qi=x then exit; inc(ps); qps:=x; nexti:=ps; end; end; procedure init; var i,j:longint; begin fillchar(d,sizeof(d),0); for i:=1 to 19 do read(si); for i:=1 to 19 do read(ti); for i:=1 to 19 do begin for

9、 j:=1 to d0+1 do if jd0 then begin inc(d0); dd0:=si; si:=d0-1; end else si:=j-1; for j:=1 to d0+1 do if jd0 then begin inc(d0); dd0:=ti; ti:=d0-1; end else ti:=j-1; end; bit1:=1; for i:=2 to 19 do biti:=biti-1*3; start:=0; target:=0; for i:=1 to 19 do begin start:=start+si*biti; target:=target+ti*biti; end; end; begin init; l:=0; r:=0; ps:=0; step:=0; insert(start); repeat l: