快捷導(dǎo)航

用C++來(lái)解決3*3拼圖的問(wèn)題

更新時(shí)間：2022年07月25日 14:12:56 作者：林三撇

這篇文章主要介紹了用C++來(lái)解決3*3拼圖的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

解決3*3拼圖的問(wèn)題

拼圖問(wèn)題

在3*3的拼圖中，如何用最少步驟拼好它，這個(gè)問(wèn)題是一個(gè)最短路徑問(wèn)題，可以使用BFS來(lái)求解，每個(gè)節(jié)點(diǎn)是一個(gè)狀態(tài)，然后得到最少步驟，中間狀態(tài)可能需要對(duì)每一個(gè)狀態(tài)進(jìn)行編碼或者散列記錄才能輸出，本代碼只解決了求最短步數(shù)，其實(shí)利用一個(gè)棧是可以實(shí)現(xiàn)打印解題過(guò)程的。

代碼

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

純C語(yǔ)言寫(xiě)的拼圖游戲

大家好，剛才整理文件，找到了自己高三？高二？時(shí)候改編的拼圖游戲，當(dāng)然，因?yàn)閏不支持圖片，所以以數(shù)字1-8代替的，算法通用。。。

聲明：

看圖片，我放到網(wǎng)盤都3年了，里面自己改編了一半，算是半原創(chuàng)，算法作者找不到了、、、

以下正文

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
int MenuReturn;
void RandMap(char map[][3]);//隨機(jī)生成數(shù)
void Game(void);//游戲主循環(huán) 
int Help(void);//游戲玩法介紹 
int About(void);
int        Menu(void);
void DealWithMenu(int MenuReturn); 
void Show(char map[][3]);
int IsWin(char map[][3]);//判斷是否達(dá)成勝利條件 
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("  數(shù)字拼圖      加q：1179307527\n\n\n");
        printf("->開(kāi)始游戲<-\n  玩法介紹  \n  關(guā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("  數(shù)字拼圖\n\n\n");
                switch (sel)
                {
                        case 1 : printf("->開(kāi)始游戲<-\n  玩法介紹  \n  關(guān)    于  \n  退出游戲  \n");break;
                        case 2 : printf("  開(kāi)始游戲  \n->玩法介紹<-\n  關(guān)    于  \n  退出游戲  \n");break;
                        case 3 : printf("  開(kāi)始游戲  \n  玩法介紹  \n->關(guān)    于<-\n  退出游戲  \n");break;
                        case 4 : printf("  開(kāi)始游戲  \n  玩法介紹  \n  關(guā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("發(fā)生未知錯(cuò)誤！\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)//隨機(jī)交換99次，這個(gè)算法不太好，容易出現(xiàn)死局 
        {
                int tem;
                j = rand()%8; 
                k = rand()%8;
                if (k-j == 1||j-k == 1||k-j == 3||j-k == 3)
                {
                        continue;//減小死局出現(xiàn)的概率，相鄰位置的數(shù)字不能交換 
                }
                tem = map[0][k];
                map[0][k] = map[0][j];
                map[0][j] = tem;
                n++;
        }//這個(gè)算法可以實(shí)現(xiàn)指定數(shù)組的亂序排列，但對(duì)本游戲不太合適，亂序不保證游戲有解 
        
        
        map[2][2] = ' ';
 
}
int Help(void)
{
        int judje = 0;
        system("cls");
        printf("點(diǎn)擊開(kāi)始游戲，程序會(huì)隨機(jī)生成一個(gè)數(shù)陣，例如\n"
                        "314\n286\n75 \n點(diǎn)擊wasd移動(dòng)數(shù)字，直至\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編程之路，從這里開(kāi)始\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);//先生成一個(gè)
        Show(Map);
        printf("任意鍵開(kāi)始游戲！！\n");
        getch();
        unsigned int t1 = time(NULL);
        while(1)
        {
                MoveNumber(Map,&Crx,&Cry);//用戶操作 
                Show(Map);
                unsigned int t2 = time(NULL);
                if(IsWin(Map))
                {
                        printf("勝利~!用時(shí)%dS",t2-t1);
                        return;
                }
        }
}

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: