C++ 實例之九宮格廣度優先遍歷

2020-01-26 14:09:59

字體：大中小

來源：轉載

供稿：網友

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; }