C++ 實(shí)例之九宮格廣度優(yōu)先遍歷
成都創(chuàng)新互聯(lián)是一家專(zhuān)注于成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),岐山網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專(zhuān)注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計(jì)領(lǐng)域的專(zhuān)業(yè)建站公司;建站業(yè)務(wù)涵蓋:岐山等地區(qū)。岐山做網(wǎng)站價(jià)格咨詢(xún):18982081108
基本思路：
廣度優(yōu)先遍歷，每次找到1的位置，分別向上、向下、向左、向右移動(dòng)。把移動(dòng)后的每個(gè)狀態(tài)存儲(chǔ)到隊(duì)列中，彈出隊(duì)頭，判斷是否為最終結(jié)果狀態(tài)，如果是，輸出遍歷的層數(shù)（即移動(dòng)步數(shù)），如果不是，把現(xiàn)階段狀態(tài)繼續(xù)執(zhí)行找到1向上向下向左向右移動(dòng)操作。
#includetypedef struct MyType { int number[3][3];int level; }MyType; MyType queue[10000]; MyType GetHead(int n) { return queue[n]; } //是否為最終結(jié)果狀態(tài) int IsFind(MyType cur) { int flag=1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { if(cur.number[i][j]!=3*i+j+1) { flag=0; break; } } return flag; } int main() { int cnt=0;//隊(duì)列中數(shù)量 int flag=0;//是否尋找到標(biāo)記 int ans=0;//最小步數(shù),也是擴(kuò)展的層數(shù) int head=0;//因?yàn)椴皇擎湵?，用head來(lái)表示第一個(gè) for(int m=0;m<3;m++) { for(int n=0;n<3;n++) { scanf("%d",&queue[cnt].number[m][n]); } } queue[cnt].level=0; cnt++; while(cnt!=0) { //出站 MyType cur=GetHead(head++); //判斷是否為最終狀態(tài) flag=IsFind(cur); if(flag==1) { printf("最小步數(shù)為:%d\n",cur.level); break; } else //不為最終狀態(tài)，進(jìn)行擴(kuò)展 { for(int row=0;row<3;row++) for(int col=0;col<3;col++) { if(cur.number[row][col]==1) //找到1,進(jìn)行擴(kuò)展 { //將1向上移 if(row!=0) { MyType temp=cur; temp.number[row][col]=temp.number[row-1][col]; temp.number[row-1][col]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //將1向右移動(dòng) if(col!=2) { MyType temp=cur; temp.number[row][col]=temp.number[row][col+1]; temp.number[row][col+1]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //將1向下移動(dòng) if(row!=2) { MyType temp=cur; temp.number[row][col]=temp.number[row+1][col]; temp.number[row+1][col]=1; temp.level=cur.level+1; queue[cnt++]=temp; } //將1向左移動(dòng) if(col!=0) { MyType temp=cur; temp.number[row][col]=temp.number[row][col-1]; temp.number[row][col-1]=1; temp.level=cur.level+1; queue[cnt++]=temp; } } } } } return 0; }
有個(gè)問(wèn)題，就是還沒(méi)弄懂，怎么判斷給定初始狀態(tài)無(wú)解，即不可能到達(dá)最終結(jié)果狀態(tài)？？
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
重慶分公司
重慶分公司
