Egiht(八种方法)
Problem Description
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
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->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
Input
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
SampleInput
2 3 4 1 5 x 7 6 8
SampleOutput
ullddrurdllurdruldr
就是给你一个序列,然后要你通过四种移动方式,回到最初的序列,输出答案,题目有SPJ,无需输出最优方法。
这道题可谓是搜索中的精髓了,最开始我就是一个简单的双向搜索,结果TLE了,看了网上的博客加了剪枝之后过了。
但是后来和队友聊这题,发现这道题的解题思路不止一种,队友说有八种
然后找到一篇博客,里面一共讲了八种解法,应该是很全面的。
博客链接:https://www.cnblogs.com/zufezzt/p/5659276.html至于我的代码就没什么好讲的了,确实用双向BFS加剪枝可以AC这道题,但这道题的精髓远远不在于此,也见识到了自己的学识浅薄。我也道不出个所以然,所以这道题我就不详细讲了。
还是那句话以梦为马,不负韶华。
最新文章
- google书签找回
- JDK里面的JRE是什么
- HDU 5878 I Count Two Three (打表+二分查找) -2016 ICPC 青岛赛区网络赛
- guava学习--File
- jquery源码学习之extend
- my linux tech object
- 深入浅出 - Android系统移植与平台开发(五)- 编译Android源码(转)
- java下载网络图片
- JSF 2 panelGrid example
- C++ STL之deque的基本操作
- 本地或者是koala软件编译less文件为css
- uva10622 Perfect P-th Powers
- Android 的权限设置大全
- sql server 2012 数据库还原方法
- hdu 4444 Walk (离散化+建图+bfs+三维判重 好题)
- 【codeforces 718 C&;D】C. Sasha and Array&;D. Andrew and Chemistry
- 跟大家谈一谈:涛舅舅家的微信域名检测api的心路历程
- Latex所有常用数学符号整理
- golang 打包,交叉编译,压缩
- Vue常见指令