C++ 實例之九宮格廣度優先遍歷。本站提示廣大學習愛好者:(C++ 實例之九宮格廣度優先遍歷)文章只能為提供參考,不一定能成為您想要的結果。以下是C++ 實例之九宮格廣度優先遍歷正文
投稿:lqh
這篇文章主要介紹了C++ 實例之九宮格廣度優先遍歷的相關資料,需要的朋友可以參考下C++ 實例之九宮格廣度優先遍歷
基本思路:
廣度優先遍歷,每次找到1的位置,分別向上、向下、向左、向右移動。把移動後的每個狀態存儲到隊列中,彈出隊頭,判斷是否為最終結果狀態,如果是,輸出遍歷的層數(即移動步數),如果不是,把現階段狀態繼續執行找到1向上向下向左向右移動操作。
#include<stdio.h> typedef struct MyType { int number[3][3];int level; }MyType; MyType queue[10000]; MyType GetHead(int n) { return queue[n]; } //是否為最終結果狀態 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;//隊列中數量 int flag=0;//是否尋找到標記 int ans=0;//最小步數,也是擴展的層數 int head=0;//因為不是鏈表,用head來表示第一個 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++); //判斷是否為最終狀態 flag=IsFind(cur); if(flag==1) { printf("最小步數為:%d\n",cur.level); break; } else //不為最終狀態,進行擴展 { for(int row=0;row<3;row++) for(int col=0;col<3;col++) { if(cur.number[row][col]==1) //找到1,進行擴展 { //將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向右移動 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向下移動 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向左移動 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; }
有個問題,就是還沒弄懂,怎麼判斷給定初始狀態無解,即不可能到達最終結果狀態??
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!