四色定理解題報(bào)告來(lái)源：JZXXOJ-10601四色定理解題報(bào)告目錄算法的基本細(xì)化題目及算法初步構(gòu)建進(jìn)一步細(xì)化程序AC2四色定理解題報(bào)告先看題目著名的四色定理你一定聽(tīng)說(shuō)過(guò)吧？這可是近代世界三大數(shù)學(xué)難題之一唷（順便提上一句，另外兩個(gè)是費(fèi)馬定理和哥德巴赫猜想）。四色定理的提出來(lái)自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯?格思里(FrancisGuthrie)在一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家著上不同的顏色?！保ㄗ⒁猓褐灰笥泄策叺膮^(qū)域不同色就可以，只有公共頂點(diǎn)的同色也沒(méi)關(guān)系）。四色定理一直都無(wú)法證明。直到1976年，在J.Koch的算法的支持下，美國(guó)數(shù)學(xué)家阿佩爾(KennethAppel)與哈肯(WolfgangHaken)在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，才終于完成了四色定理的證明。你的任務(wù)相對(duì)那些數(shù)學(xué)家們來(lái)說(shuō)當(dāng)然要容易得多：你只要編寫(xiě)一個(gè)程序，計(jì)算一下在給定的一張有5個(gè)區(qū)域的地圖上，用四種顏色填充不同區(qū)域，并保證有公共邊的區(qū)域不同色的方案數(shù)有多少就可以了。3四色定理解題報(bào)告輸入輸出及樣例輸入第一行是一個(gè)整數(shù)N（０≤N≤10），分別表示地圖中有公共邊的區(qū)域的信息數(shù)量。下面N行，每行一對(duì)整數(shù)，表示對(duì)所有區(qū)域編號(hào)之后，此兩個(gè)編號(hào)的區(qū)域是有公共邊的。

輸出只有一個(gè)整數(shù)，表示用四種顏色填充地圖的總方案數(shù)。注意，在某些方案中，所有四種顏色不必都用到。inputoutput4324121314154四色定理解題報(bào)告題意分析

看到這題我想到一個(gè)單詞:water。我想：這題應(yīng)該用深搜做，階段是當(dāng)前填完了多少格子。

但是，理想很豐滿(mǎn)，現(xiàn)實(shí)很骨感。我編好框架就傻眼了。

言歸正傳，剛剛說(shuō)了階段是當(dāng)前填完了多少格子，那么，每個(gè)階段要干嘛呢？1.判斷是否填完，填完則找到一種解（本題是求解總數(shù)）。2.枚舉k位置上所有可能的顏色。3.若顏色可以填則填進(jìn)去，填k+1號(hào)格子，現(xiàn)場(chǎng)恢復(fù)。5四色定理解題報(bào)告一級(jí)算法開(kāi)始PROsearch(k)if到達(dá)邊界then

增加解總數(shù)，返回

枚舉k位置上所有可能的顏色iif顏色i符合條件then現(xiàn)場(chǎng)保存search（k+1）現(xiàn)場(chǎng)恢復(fù)Main

輸入，初始化，預(yù)處理，進(jìn)行第一階段枚舉，輸出結(jié)束6四色定理解題報(bào)告算法的基本細(xì)化

增加解總數(shù)的方法是inc（total)。

我們可以加一個(gè)pd函數(shù)，用來(lái)判斷顏色是否可以填。

第一階段枚舉時(shí)也要做現(xiàn)場(chǎng)保存和現(xiàn)場(chǎng)恢復(fù)這些工作，主程序調(diào)用search參數(shù)是2。

預(yù)處理可以把基本數(shù)據(jù)變成鄰接表。

7四色定理解題報(bào)告代碼碎片1:深搜proceduresearch(k:longint);vark1:longint;beginifk=6thenbegininc(total);exit;end;fork1:=1to4dobeginb[k]:=k1;

ifpd(k)thenbeginsearch(k+1);b[k]:=0;end;b[k]:=0;end;end;k1是枚舉k顏色的量。pd（k）的意思是位置k上填顏色k1。b數(shù)組是存儲(chǔ)顏色的數(shù)組。8四色定理解題報(bào)告代碼碎片2:判斷functionpd(m:longint):boolean;vari2:longint;beginpd:=true;fori2:=1to5dobeginif(a[m,i2]=1)and(b[m]=b[i2])thenbeginpd:=false;break;

end;end;end;用循環(huán)枚舉每個(gè)區(qū)域(a[m,i2]=1)判斷兩個(gè)區(qū)域是否相鄰。(b[m]=b[i2])判斷顏色是否相同。9四色定理解題報(bào)告代碼碎片3:預(yù)處理fori:=1tondobeginreadln(i1,j1);a[i1,j1]:=1;a[j1,i1]:=1;end;a[i1,j1]:=1;a[j1,i1]:=1;改成鄰接表。10四色定理解題報(bào)告代碼拼接varn,total,i,j,i1,j1:longint;a:array[1..5,1..5]oflongint;b:array[1..5]oflongint;functionpd(m:longint):boolean;vari2:longint;beginpd:=true;fori2:=1to5dobeginif(a[m,i2]=1)and(b[m]=b[i2])thenbeginpd:=false;break;end;end;end;proceduresearch(k:longint);vark1:longint;beginifk=6thenbegininc(total);exit;end;fork1:=1to4dobeginb[k]:=k1;ifpd(k)thenbeginsearch(k+1);b[k]:=0;end;b[k]:=0;end;end;beginreadln(n);fori:=1to5doforj:=1to5doa[i,j]:=0;fori:=1tondobeginreadln(i1,j1);a[i1,j1]:=1;a[j1,i1]:=1;end;total:=0;fori:=1to4dobeginb[1]:=i;search(2);b[1]:=0;end;end;writeln(total);end.11四色定理解題報(bào)告AC感言

說(shuō)句大實(shí)話(huà)，這次AC，我自己付出了許多努力。

就像周鎮(zhèn)東說(shuō)的，人生就像編程，一次次優(yōu)化，一次次修改?，F(xiàn)在，我想說(shuō)，人生中會(huì)有許多if語(yǔ)句，你做的每件事都是一個(gè)子程序，但是，除非遇到halt，絕不exit出這個(gè)子程序……

我想說(shuō)的還有很多很多，但總結(jié)成一句話(huà)：

偉大的人不會(huì)踢開(kāi)面前的石子，更不會(huì)繞開(kāi)它。偉大的人不懼怕困難，他