用C++来解决3*3拼图的问题
解决3*3拼图的问题
拼图问题
在3*3的拼图中，如何用最少步骤拼好它，这个问题是一个最短路径问题，可以使用BFS来求解，每个节点是一个状态，然后得到最少步骤，中间状态可能需要对每一个状态进行编码或者散列记录才能输出，本代码只解决了求最短步数，其实利用一个栈是可以实现打印解题过程的。
代码
#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语言写的拼图游戏
大家好，刚才整理文件，找到了自己高三？高二？时候改编的拼图游戏，当然，因为c不支持图片，所以以数字1-8代替的，算法通用。。。
声明：
看图片，我放到网盘都3年了，里面自己改编了一半，算是半原创，算法作者找不到了、、、
以下正文
#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;
}
}
}以上为个人经验，希望能给大家一个参考，也希望大家多多支持。
相关文章