「Luogu1379」八数码

Source and Judge

经典问题
Luogu1379
Caioj1046

Problem

「Description」
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。
棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。
要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
「Input」
输入初始状态,一行九个数字,空格用0表示。
「Output」
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
「Limited conditions」

「Sample input」
283104765
「Sample output」
4
「Sample explanation」

Record

30min

Analysis

请先思考后再展开

这道题可谓搜索算法的超级经典入门题
然后方法也灰常多,康托展开(如今看来没有什么卵用,而且想想就知道了)、bool数组乱搞
那么今天因为要用到A*算法,打算用这道题试一试
然后网上看到一个大概是acmer的,炒鸡变态地用八种做法做了:强烈推介

那关于A*的做法教程,这篇文章还是挺好的:this

Code

请先思考后再展开

然鹅我并不想打搜索题了……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6628.html
转载请注明出处,谢谢!