[C++算法設計]八數碼問題

八數碼問題 【題意】 編好為1~8的8個正方形滑塊擺成3行3列（一個格子為空），如圖所示 每次可以移動空格相鄰的滑塊到空格，要計算出能移動出目標局面的最小步數，如無法達到則輸出-1。   【分析】 我們可以把每一種局面定義為一種“狀態”，而每個狀態就是由9個格子的編號依次排列組成，如上圖左的狀態為：1,5,2,4,3,0,7,8,6，同理右的狀態為：1,2,3,4,5,6,7,8,0。然後我們可以用寬度優先遍歷搜索（BFS）的方法，對每一種狀態都進行擴展出新的狀態，然後知道搜索出目標狀態為止。 【代碼】  

typedef int State[9];       //定義“狀態”類型  
const int Maxstate = 1000000;  
State st[Maxstate],goal;    //狀態數組  
int dist[Maxstate];       
//如果要打印方案，還要定義一個父親編號數組 int fa[Maxstate];  
  
const int dx[]={-1,1,0,0};  
const int dy[]={0,0,-1,1};  
  
void init(){}       //初始化函數  
  
int bfs()  
{  
    init();  
    int front=1;  
    int rear=2;  
    while(front<rear)  
    {  
        State& s = st[front];  
        if(memcmp(goal,s,sizeof(s))==0) return front;  
        int z;  
        for(z=0;z<9;z++) if(!s[z]) break;  
        int x=z/3,y=z%3;  
        for (int d=0;d<4;d++)  
        {  
            int newx=x+dx[d];  
            int newy=y+dy[d];  
            int newz=newx*3+newy;  
            if(newx>=0 && newx<3 && newy>=0 &&newy<3)  
            {  
                State& t=st[rear];  
                memcpy(&t,&s,sizeof(s));  
                t[newz]=s[z];  
                t[z]=s[newz];  
                dist[rear]=dist[front]+1;  
                if(insert(rear)) rear++;    //判重  
            }  
        }  
        front++;  
    }  
    return 0;  
}  

 

    上面這段代碼缺少一個main()函數，一個init()函數和一個判重的insert()函數，我覺著比較重要的一個點時定義“狀態”類型的寫法，我開始覺著應該是typedef int[9] State這麼寫的，但是不對，具體為什麼要那麼寫我也不清楚，反正很容易寫錯。然後就是最關鍵的bfs函數中用了很多“引用”，這可以學習一下，這樣做很方便，比指針好理解。