Rhythm of Codes

BZOJ 1054移动玩具 题解 BFS暴力求解

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 1884 Solved: 1033

[Submit][Status][Discuss]

Description

在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动

时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移

动到某人心中的目标状态。

Input

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空

行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

Output

一个整数,所需要的最少移动次数。

 

Sample Input

1111

0000

1110

0010

 

1010

0101

1010

0101

Sample Output

4

这道题第一眼看过去就跟codevs的四子连棋很像,只不过这道题的空白点数量不确定。对于求最短步数的搜索我们可以迭代加深搜索或者bfs,但针对这道题迭代的话过于麻烦,那么我们就直暴力bfs+判重。对于判重,我们可以分析下棋盘,棋盘只有4×4十六个点,每个点只有0,1两种状态,我们可以将每种棋盘的状况用一个数字存下来,这个数字不会超过 216 (大概六万多一点),然后用一个status数组判断这种情况是否访问过。

 

 

其实这道题还有别的思路,我们可以将每种情况枚举出来,然后建图。 读入时,用cnt记录棋盘中1的数目,再枚举一下所有有cnt个1的棋盘,每个棋盘用它的二进制数字作为序号来建点。如果两个棋盘只有1步之差,那么我们给他们连上一个权值为1的边。连边完成后,我们就可以用spfa或dijkstra来求起始棋盘到目标棋盘的最短路。这个最短路就是最短步数。不过明显bfs更快捷一点。

 

Leave a Reply

Your email address will not be published. Required fields are marked *