C++ 實(shí)例之九宮格廣度優(yōu)先遍歷

創(chuàng)新互聯(lián)建站專注于巴林右旗網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供巴林右旗營銷型網(wǎng)站建設(shè)，巴林右旗網(wǎng)站制作、巴林右旗網(wǎng)頁設(shè)計(jì)、巴林右旗網(wǎng)站官網(wǎng)定制、微信小程序服務(wù)，打造巴林右旗網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供巴林右旗網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

基本思路：

廣度優(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)操作。

#include 
 
typedef 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)椴皇擎湵恚胔ead來表示第一個(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; 
} 

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前題目：C++實(shí)例之九宮格廣度優(yōu)先遍歷-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://weahome.cn/article/dsdggi.html