第C++算法學(xué)習(xí)之回溯法的應(yīng)用for(inti=1;ii++){

a[t][i]=1-(a[t+1][i]+a[t+1][i+1])%2;//遞推第t層i列的符號(hào)

if(a[t][i])//若為＋

sum2++;

if(2*(sum1+sum2)==(n*(n+1)/2))//記錄+總數(shù)是否為符號(hào)總數(shù)的一半

sum++;

voiddfs(intx){//x表示考慮頂層第x個(gè)位置的符號(hào)

for(inti=0;ii++){

//0=1=+

if(i)

sum1++;//記錄頂層+的數(shù)量

a[n][x]=i;

if(x==n)//考慮完頂層的一種符號(hào)擺放，進(jìn)行檢查

check();

else

dfs(x+1);

if(i)

sum1--;//若上擺放為+，則+數(shù)量回退1

intmain()

cinn;

if((n*(n+1)/2)%2==1)//判斷符號(hào)總數(shù)奇偶性

cout0endl;

else{

dfs(1);

coutsumendl;

return0;

算法分析與知識(shí)點(diǎn)：

本題主要運(yùn)用回溯的思想，這題的特點(diǎn)是不能輸入元素，而且只要確定的頂層的n的符號(hào)的排列情況，就可以得到整個(gè)符號(hào)三角形的排列情況，因此只需要對(duì)符號(hào)三角形的頂層進(jìn)行遍歷就好了。題目中有要求+和-的數(shù)量要一樣，所以符號(hào)三角形的符號(hào)總數(shù)要是偶數(shù)，否則解決方案數(shù)為0。

令0和1分別代表-和+，其他層在頂層確定后即確定了，不需要枚舉。采用dfs對(duì)第一層的符號(hào)排列情況進(jìn)行遍歷，遍歷完n后就可得到答案。

回溯堂練

實(shí)驗(yàn)題目：森林迷宮

題目描述：

一天Luna在森林里探險(xiǎn)的時(shí)候不小心走入了一個(gè)迷宮，迷宮可以看成是由n*n的格點(diǎn)組成，每個(gè)格點(diǎn)只有2種狀態(tài)：^和#；前者表示可以通行后者表示不能通行。當(dāng)Luna處在某個(gè)格點(diǎn)時(shí)，她只能移動(dòng)到東南西北(或者說(shuō)上下左右)四個(gè)方向之一的相鄰格點(diǎn)上，Luna想要從起點(diǎn)A走到終點(diǎn)B（中途不能走出迷宮）。如果起點(diǎn)或者終點(diǎn)有一個(gè)不能通行(為#)，則當(dāng)做無(wú)法通行。

輸入要求：

第1行是測(cè)試數(shù)據(jù)的組數(shù)k，后面跟著k組輸入。

每組測(cè)試數(shù)據(jù)的第1行是一個(gè)正整數(shù)n(1=n=100)，表示迷宮的規(guī)模是n*n的。

接下來(lái)是一個(gè)n*n的矩陣，矩陣中的元素為.或者#。

再接下來(lái)一行是4個(gè)整數(shù)ar,ac,br,bc。表示A處在第ar行，第ac列，B處在第br行,第bc列。注意坐標(biāo)ar，ac，br，bc全部是從0開始計(jì)數(shù)的類似[1,4][5,6]被認(rèn)為是覆蓋了[1,6]。

輸出要求：

YES或NO

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

chars[105][105];//記錄地圖

intn,ha,la,hb,lb,dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}},flag;//flag標(biāo)記搜索完畢后是否能到達(dá)終點(diǎn)

voiddfs(intha,intla)

if(ha==hbla==lb)//判斷是否達(dá)到終點(diǎn)

flag=1;

if(flag){

cout"YES"endl;

return;

for(inti=0;ii++)

intdx=ha+dir[i][0];

intdy=la+dir[i][1];

if(dx=0dxndy=0dyns[dx][dy]=='^')

s[dx][dy]='#';//只走一次，每個(gè)方都要走一遍，只要連通，肯定能到終點(diǎn)

dfs(dx,dy);

intmain()

intk;

cink;

while(k--)

cinn;

for(inti=0;ii++)for(intj=0;jj++)cins[i][j];

cinhalahblb;

if(s[ha][la]=='#'||s[hb][lb]=='#')cout"NO"endl;//提前判斷始點(diǎn)和終點(diǎn)是否符合要求

else

flag=0;

dfs(ha,la);//dfs搜索路徑

if(flag==0)cout"NO"endl;

return0;

算法分析與知識(shí)點(diǎn)：

本采用深度優(yōu)先的搜索方式來(lái)搜索全部路徑，大致思路為：從當(dāng)前點(diǎn)出發(fā)，往四個(gè)方位探尋找出所有與之相鄰的且尚未被訪問(wèn)過(guò)的點(diǎn)，從中暫時(shí)先選取一個(gè)點(diǎn)作為當(dāng)前點(diǎn)繼續(xù)上述過(guò)程，直到到達(dá)目的地或者再也無(wú)法探尋到能前進(jìn)的點(diǎn)，再返回。如果當(dāng)前搜索的點(diǎn)到達(dá)了目標(biāo)點(diǎn)，flag標(biāo)記為true，返回即可。若所有能到達(dá)的點(diǎn)都搜索完了，flag仍為false，則無(wú)法到達(dá)。

實(shí)驗(yàn)題目：地圖著色

題目描述：

給定圖G=(V,E)，需要為圖G的各頂點(diǎn)著色，是否有一種著色法使G中相鄰的兩個(gè)頂點(diǎn)有不同的顏色

輸入要求：

第一行是頂點(diǎn)的個(gè)數(shù)n（2n10），顏色數(shù)m（1mn）。

接下來(lái)是頂點(diǎn)之間的連接關(guān)系：ab；表示a和b相鄰。頂點(diǎn)從1開始計(jì)。

當(dāng)a，b同時(shí)為0時(shí)表示輸入結(jié)束。

輸出要求：

輸出著色方案總數(shù)和最少顏色數(shù)。如果無(wú)可行方案，顏色數(shù)為0。

實(shí)驗(yàn)代碼及注釋:

#includebits/stdc++.h

usingnamespacestd;

#defineN10

intn,sum=0,m;

intx[N+1];//記錄可行解

intg[N+1][N+1];//鄰接矩陣

intans=N;

intok(intt)//判斷當(dāng)前層節(jié)點(diǎn)是否可行

for(intj=1;jj++)

if(g[t][j]==1x[t]==x[j])

return0;

return1;

intnum_m(){//計(jì)算可行解中的顏色種類數(shù)

intans=0;

inttemp[101]={0};

for(inti=1;ii++){

temp[x[i]]=1;

for(inti=1;i=100;i++)

ans+=temp[i];

returnans;

voidback_track(intt)

inti;

if(tn)

sum++;//找到可行解，總數(shù)+1

//for(i=1;ii++)

//printf("%d",x[i]);

//printf("\n");

intxx=num_m();

if(xxans)

ans=xx;

else

for(inti=1;ii++)//遍歷節(jié)點(diǎn)的每種顏色取值

x[t]=i;

if(ok(t))

back_track(t+1);

x[t]=0;

intmain()

cinnm;//n個(gè)頂點(diǎn)，m種顏色

inta,b;

cinab;

while(!(a==0b==0)){//構(gòu)造鄰接矩陣

g[a][b]=1;

g[b][a]=1;

cinab;

back_track(1);

if(sum)

coutsum""ansendl;

else

cout0""0endl;

return0;

算法分析與知識(shí)點(diǎn)：

這個(gè)問(wèn)題和八皇后還有求子集和等問(wèn)題都具有類似之處，其核心在通過(guò)遍歷找到所有的問(wèn)題子集，但是在遞歸遍歷的時(shí)候，都在加一個(gè)判斷，將那些明顯不滿足條件的情況給直接排出，減少問(wèn)題的規(guī)模，其實(shí)這類問(wèn)題，在遞歸遍歷的時(shí)候都是類似與對(duì)一顆樹的便利每個(gè)節(jié)點(diǎn)相當(dāng)走到此時(shí)的狀態(tài)，然后再判斷此時(shí)的狀態(tài)是否能繼續(xù)走下去，如果不能就將其回溯到上一個(gè)節(jié)點(diǎn)，避免浪費(fèi)時(shí)間。

給定圖g（v，e）和m種顏色，如果這個(gè)圖不是m可著色，給出否定回答，是的話找出所有不同著色法。

分析：

用鄰接矩陣表示圖g，如果頂點(diǎn)i跟j之間有邊，則g[i][j]=1,否則g[i][j]=0.用整數(shù)1，2，，m表示m種顏色，頂點(diǎn)i的顏色用x[i]表示，所以x[1：n]是一種著色方案。