1225 八数码难题

1225 八数码难题

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

题解

 查看运行结果

题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们. 问题描述 在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

输入描述 Input Description

输入初试状态,一行九个数字,空格用0表示

输出描述 Output Description

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 Sample Input

283104765

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

详见试题

分类标签 Tags 点此展开 

代码有点乱

思路还算清晰

bfs+hash判重

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 const int MAXN=5;
  6 int xx[5]={-1,+1,0,0};
  7 int yy[5]={0,0,-1,+1};
  8 struct node
  9 {
 10     int mp[MAXN][MAXN];
 11 }a[100001];
 12 int hashfind[3733801];
 13 int step[200];
 14 int h=0,t=1;
 15 int bc[MAXN][MAXN]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};
 16 int hash()
 17 {
 18     int s=0;
 19     int k=1;
 20     for(int i=1;i<=3;i++)
 21     {
 22         for(int j=1;j<=3;j++)
 23         {
 24             s=s+a[t].mp[i][j]*k;
 25             k=k*7;
 26         }
 27     }
 28     s=s%3733801;
 29     if(hashfind[s]==0)
 30     {
 31         hashfind[s]=1;
 32         return 1;
 33     }
 34     else
 35     {
 36         return 0;
 37     }
 38 }
 39 int check()
 40 {
 41     for(int i=1;i<=3;i++)
 42     {
 43         for(int j=1;j<=3;j++)
 44         {
 45             if(a[t].mp[i][j]!=bc[i][j])
 46             return 0;
 47         }
 48     }
 49     return 1;
 50 }
 51 void move(int x,int y)
 52 {
 53     
 54     for(int i=0;i<4;i++)
 55     {
 56         int wx=x+xx[i];
 57         int wy=y+yy[i];
 58         if(wx>=1&&wx<=3&&wy>=1&&wy<=3)
 59         {
 60             for(int j=1;j<=3;j++)
 61             {
 62                 for(int k=1;k<=3;k++)
 63                     {
 64                         a[t].mp[j][k]=a[h].mp[j][k];
 65                     }
 66             }
 67             swap(a[t].mp[wx][wy],a[t].mp[x][y]);
 68             step[t]=step[h]+1;
 69             if(check()==1)
 70             {
 71                 printf("%d",step[t]);
 72                 exit(0);// end
 73             }
 74             if(hash()==1)
 75             t++;
 76         }
 77     }
 78 }
 79 void bfs()
 80 {
 81     while(h<t)
 82     {
 83         for(int i=1;i<=3;i++)
 84         {
 85             for(int j=1;j<=3;j++)
 86             {
 87                 if(a[h].mp[i][j]==0)
 88                 {
 89                     move(i,j);
 90                 }
 91             }
 92         }
 93         h++;
 94     }
 95 }
 96 int main()
 97 {
 98     char dr[10];
 99     int bgx=0;
100     int bgy=0;
101     gets(dr);
102     int now=0;
103     for(int i=1;i<=3;i++)
104     {
105         for(int j=1;j<=3;j++)
106         {
107             a[0].mp[i][j]=dr[now]-48;
108             if(a[0].mp[i][j]==0)
109             {
110                 bgx=i;
111                 bgy=j;
112             }
113             now++;
114         }
115     }
116     bfs();
117     return 0;
118 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏web编程技术分享

用canvas制作彩虹球喷枪(js面向对象小案例)

4106
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

1001
来自专栏python爬虫实战之路

使用bloomfilter修改scrapy-redis去重

这篇文章憋的太久了,断断续续战线拉了好长。这个也是属于喜马拉雅那个项目的一部分,还要再忙一阵子。请大家见谅。

2022
来自专栏清墨_iOS分享

OpenGLES-04 绘制带颜色的立方体

前面几篇文章都只是绘制了平面图形,接下来我们开始绘制一个真正的3D立方体图形。代码在前一篇文章基础上修改。 绘制立方体之前,我们需要知道这个立方体的各个顶点坐...

3999
来自专栏数据结构与算法

1226 倒水问题

1226 倒水问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有两个无刻...

2856
来自专栏数据结构与算法

agc027D - Modulo Matrix(构造 黑白染色)

构造一个$n * n$的矩阵,要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

963
来自专栏数据结构与算法

cf1027F. Session in BSU(并查集 匈牙利)

$n$个人,每个人可以在第$a_i$天或第$b_i$,一天最多考一场试,问在最优的情况下,最晚什么时候结束

1231
来自专栏尾尾部落

[LeetCode]Palindrome Number回文

链接:https://leetcode.com/problems/palindrome-number/#/description 难度:Easy 题目:De...

1202
来自专栏数说工作室

【SAS Says】基础篇:描述性分析(下)

好吧,这一节是留给处女座的,主要说如何用proc tabulate和proc report产生一个更加耐看的报告。有时候print、means和freq产生的报...

5495
来自专栏菩提树下的杨过

Flash/Flex学习笔记(19):颜色合成与分解的基本原理

传统的RGB颜色体系中,每一个分量值的范围都是0到255,如果转换为2进制的话最多需要8位(比如:十进制的255变成二进制则为11111111),三个分量加起来...

2238

扫码关注云+社区

领取腾讯云代金券