| 题目名称 | 3506. [POJ 1077]八数码(Eight) |
|---|---|
| 输入输出 | neweight.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 gao
于2020-11-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：5， 通过率：60% | ||||
 zhk |
100 | 0.056 s | 2.50 MiB | C++ |
|
zhk |
100 | 0.067 s | 3.07 MiB | C++ |
|
lihaoze |
100 | 3.677 s | 6.77 MiB | C++ |
|
zhk |
60 | 0.056 s | 2.47 MiB | C++ |
|
zhk |
0 | 10.000 s | 5.73 MiB | C++ |
| 关于 八数码(Eight) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题没写special judge
zhk
2022-02-27 15:50
2楼
| ||||
|
这一题移动方式可迷
lihaoze
2022-01-18 12:09
1楼
| ||||
【题目描述】
4×4的棋盘，由15块滑动棋子构成，每一块上面都有1到15个数字，其中一块缺失。将缺失的棋子标为“x”；空格周围的棋子可以移到空格中，要求解的问题是：给出一种初始状态和目标状态，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
目标状态排列如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x下面就是一个移动的例子：
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->
在这个问题中，要求编写一个程序来解决8数码问题，它由一个3×3的棋盘组成，目标状态为：
1 2 3 4 5 6 7 8 x
【输入格式】
一行9个数字，描述初始状态
【输出格式】
如果不能完成目标状态，则输出"unsolved"
或者将一个完全由字母"r"、"l"、"u"和"d"组成的字符串打印到标准输出,表示"x"移动的路径
【样例输入】
2 3 4 1 5 x 7 6 8
【样例输出】
ullddrurdllurdruldr
【来源】
《算法竞赛进阶指南》POJ 1077