用C++来解决3*3拼图的问题

#include<bits/stdc++.h> 
using namespace std;

typedef int State[9];
const int maxstate=1000000;
State st[maxstate],Goal;
int dist[maxstate];

const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int vis[362880],fact[9];

void init_lookup_table(){
    fact[0]=1;
    for(int i=1;i<9;i++)    fact[i]=fact[i-1]*i;
}
int try_to_insert(int s){
    int code=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++)  if(st[s][j]<st[s][i])   cnt++;
        code+=fact[8-i]*cnt;
    }
    if(vis[code])   return 0;
    return vis[code]=1;
}
int bfs(){
    init_lookup_table();
    int front=1,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(try_to_insert(rear)) rear++;
            }
        }
        front++;
    }
    return 0;
}
int main(){
    freopen("F://inp.txt","r",stdin);
    for(int i=0;i<9;i++)    cin>>st[1][i];
    for(int i=0;i<9;i++)    cin>>goal[i];
    for(int i=0;i<9;i++){if(i&&i%3==0)  cout<<endl;cout<<st[1][i]<<" ";}
    int ans=bfs();
    if(ans>0)   printf("\nNeed %d steps come out!\n",dist[ans]);
    else    printf("\nNo way!\n");
    for(int i=0;i<9;i++){if(i&&i%3==0)  cout<<endl;cout<<goal[i]<<" ";}
    return 0;
}

#include <stdio.h>
#include <coNIO.h>
#include <stdlib.h>
#include <time.h>
int MenuReturn;
void RandMap(char map[][3]);//随机生成数
void Game(void);//游戏主循环 
int Help(void);//游戏玩法介绍 
int About(void);
int        Menu(void);
void DealWithMenu(int MenuReturn); 
void Show(char map[][3]);
int IsWin(char map[][3]);//判断是否达成胜利条件 
int main(void)
{
        system("color 1E");
        while(1)
        {
                MenuReturn = Menu();
                DealWithMenu(MenuReturn);
        }
        return 0;
} 
int        Menu(void)
{
        int sel = 1;
        int tem = 0;
        char kb;
        system("cls");
        printf("  数字拼图      加q：1179307527\n\n\n");
        printf("->开始游戏<-\n  玩法介绍  \n  关    于  \n  退出游戏  \n");
        do{
                kb = getch();
                switch(kb)
                {
                        case 'w' : tem--;sel += tem;break;
                        case 's' : tem++;sel += tem; break;        
                        default  : NULL ; break;
                }
                tem = 0;
                if (sel == 0)
                {
                        sel = 4;
                }
                if (sel == 5)
                {
                        sel = 1;
                }
                system("cls");
                printf("  数字拼图\n\n\n");
                switch (sel)
                {
                        case 1 : printf("->开始游戏<-\n  玩法介绍  \n  关    于  \n  退出游戏  \n");break;
                        case 2 : printf("  开始游戏  \n->玩法介绍<-\n  关    于  \n  退出游戏  \n");break;
                        case 3 : printf("  开始游戏  \n  玩法介绍  \n->关    于<-\n  退出游戏  \n");break;
                        case 4 : printf("  开始游戏  \n  玩法介绍  \n  关    于  \n->退出游戏-<\n");break;
                        default: return-1; break; 
                }
        }while(kb != '\r');
 
        return sel;
}
void DealWithMenu(int MenuReturn)
{
        int retu;
        switch(MenuReturn)
        {
                case 1 : Game();break;
                case 2 : retu = Help();break;
                case 3 : retu = About();break;
                case 4 : exit(0);break;
                case -1: printf("发生未知错误！\n");        
        }
 
}
void Show(char map[][3])
{
        int i,j;
        system("cls");
        for(i=0;i<3;i++)
        {
                for(j=0;j<3;j++)
                {
                        printf("%2c",map[i][j]);
                }
                printf("\n");
        }
        
        return;
}
void MoveNumber(char map[][3],int *Crx,int *Cry)
{
        enum {UP,DOWN ,LEFT ,RIGHT};
        int kb;
        int dx = 0,dy = 0;
        switch(getch())
        {
                case 'w' :dy--;kb = UP;  break;
                case 's' :dy++;kb = DOWN;break;
                case 'a' :dx--;kb = LEFT;break;
                case 'd' :dx++;kb = RIGHT;break;
                default  :NULL;break; 
        }
        if(kb == UP&& *Cry+1<=2)
        {
                map[*Cry][*Crx] = map[*Cry+1][*Crx];
                map[*Cry+=1][*Crx] = ' ';
        }
        if(kb == DOWN&&*Cry-1>=0)
        {
                map[*Cry][*Crx] = map[*Cry-1][*Crx];
                map[*Cry-=1][*Crx] = ' ';
        }
        if(kb == LEFT&&        *Crx+1<=2)
        {
                map[*Cry][*Crx] = map[*Cry][*Crx+1];
                map[*Cry][*Crx+=1] = ' ';
        }
        if(kb ==RIGHT&& *Crx-1>=0)
        {
                map[*Cry][*Crx] = map[*Cry][*Crx-1];
                map[*Cry][*Crx-=1] = ' ';
        }
        
        return;
}
void RandMap(char map[][3])
{
        
        int i,j,k,n = 0;
        srand((unsigned)time(NULL));
        for(i = 0;i<8;i++)
        {
                map[0][i] = '1'+i;
        }
        while(n<99)//随机交换99次，这个算法不太好，容易出现死局 
        {
                int tem;
                j = rand()%8; 
                k = rand()%8;
                if (k-j == 1||j-k == 1||k-j == 3||j-k == 3)
                {
                        continue;//减小死局出现的概率，相邻位置的数字不能交换 
                }
                tem = map[0][k];
                map[0][k] = map[0][j];
                map[0][j] = tem;
                n++;
        }//这个算法可以实现指定数组的乱序排列，但对本游戏不太合适，乱序不保证游戏有解 
        
        
        map[2][2] = ' ';
 
}
int Help(void)
{
        int judje = 0;
        system("cls");
        printf("点击开始游戏，程序会随机生成一个数阵，例如\n"
                        "314\n286\n75 \n点击wasd移动数字，直至\n123\n456\n78 \n则胜出\n");
        printf("返回菜单吗？\t   =====   y/n\n");
        do{
                int ch = getchar();
                if(ch == 'y')
                {
                        return 1;
                }
                if(ch == 'n')
                {
                        judje = 1;
                }
        }while(judje == 1);
} 
int About(void)
{
        int judje = 0;
        system("cls"); 
        printf("本游戏由莫言情难忘改编\n编程之路，从这里开始\n");
        printf("返回菜单吗？\t   ======    y/n\n");
        do{
                int ch = getchar();
                if(ch == 'y')
                {
                        return 1;
                }
                if(ch == 'n')
                {
                        judje = 1;
                }
        }while(judje == 1);
}
int IsWin(char map[][3])
{
        int i;
        int j = 0;
        for(i = 0;i<8;i++)
        {
                if (map[0][i] == '1'+i)
                j++;
        }
 
   if (j == 8)
   {
                   return 1;
   }
   else 
   {
                   return 0;
   }
 
 
} 
void Game(void)
{
        char Map[3][3] = {0};
        int Crx = 2;
        int Cry = 2;
        RandMap(Map);//先生成一个
        Show(Map);
        printf("任意键开始游戏！！\n");
        getch();
        unsigned int t1 = time(NULL);
        while(1)
        {
                MoveNumber(Map,&Crx,&Cry);//用户操作 
                Show(Map);
                unsigned int t2 = time(NULL);
                if(IsWin(Map))
                {
                        printf("胜利~!用时%dS",t2-t1);
                        return;
                }
        }
}