溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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;
}
有個問題，就是還沒弄懂，怎么判斷給定初始狀態無解，即不可能到達最終結果狀態？？
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
