程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ 實例之九宮格廣度優先遍歷

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

編輯:關於C++

C++ 實例之九宮格廣度優先遍歷。本站提示廣大學習愛好者:(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; 
} 



有個問題,就是還沒弄懂,怎麼判斷給定初始狀態無解,即不可能到達最終結果狀態??

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved