当前位置:首页 > 搜索 > 广度优先搜索 > 正文
洛谷P2578[ZJOI2005]九数码游戏
3624+

题目大意:与八数码游戏相似,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!种状态,不会超时。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

洛谷P2578[ZJOI2005]九数码游戏:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!