洛谷P2578[ZJOI2005]九数码游戏
4251+
作者：crxis 发布：2017-06-16 分类：广度优先搜索
题目大意：与八数码游戏相似，9个格子里面分别有0-8这9个数字，按照一定的移动规则，最少多少步能到达目标状态呢？（CodeVS 2466）
题目描述
输入输出格式
输入格式：
输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。
输出格式：
如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。
否则，第一行是一个整数S，表示最少的操作次数。接下来4 × (S + 1)行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。
输入输出样例
输入样例#1：
2 3 0 1 8 7 5 4 6
输出样例#1：
4 2 3 0 1 8 7 5 4 6 1 2 3 5 8 0 4 6 7 1 2 3 0 5 8 4 6 7 0 1 2 4 5 3 6 7 8 0 1 2 3 4 5 6 7 8
解题思路
用一个int范围的数存储拼盘状态，预先处理好两种变化的转移，用哈希表判断是否重复；使用广度优先搜索一直搜索到目标状态，至多9!种状态，不会超时。
程序实现
