题解 P4289 【[HAOI2008]移动玩具】
Createsj
2018-11-09 13:17:29
### [博客食用效果更佳~](https://createsj.blog.luogu.org/solution-p4289)
让我们先来看看题目：
### 题目描述
在一个 $4*4$ 的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
### 输入输出格式
#### 输入格式：
前 $4$ 行表示玩具的初始状态，每行 $4$ 个数字 $1$ 或 $0$，$1$ 表示方格中放置了玩具，$0$ 表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行 $4$ 个数字 $1$ 或 $0$，意义同上。
#### 输出格式：
一个整数，所需要的最少移动次数。
事实上，当看到 $4\times4$ 和 $1$ 或 $0$ 时，就应该想到状压了，因为只有 $4\times 4 =16$ 个方格，而每个方格只有 $1$ 或 $0$ 两种状态，所以总共只有 $2^{16}=65536$ 种状态（由于玩具的个数是一定的，所以状态数还要小得多，不过状压到 $65536$ 种已经够用了），一个 unsigned short 就可以储存下来了。为了方便起见，这里我为 unsigned short 取一个别名 ushort。
```cpp
typedef unsigned short ushort;
```
接下来我们来写输入函数用于输入起始和目标状态：
```cpp
inline bool getbool()//输入一个bool值（即 0 或 1）
{
char c;
do
c=getchar();
while(c!='1' && c!='0');
return c&1;
}
ushort input()
{
ushort num=0;
for(ushort i=0;i<16;++i)
num=(num<<1)|getbool();//num 左移一位后在后面插入一个bool值（0或1）
return num;
}
```
接下来就是解决移动玩具的问题了。
比如样例的初始状态为：
$1\quad1\quad1\quad1$
$0\quad0\quad0\quad0$
$1\quad1\quad1\quad0$
$0\quad0\quad1\quad0$
按照我给出的输入函数，初始状态被保存为二进制数
$1111000011100010$
我们想要第 $0$ 行第 $0$ 列的玩具向下移动，即使初始状态变为：
$0\quad1\quad1\quad1$
$1\quad0\quad0\quad0$
$1\quad1\quad1\quad0$
$0\quad0\quad1\quad0$
保存为
$0111100011100010$
很显然，这相当于交换两位数。
可以想到，我们可以先用 $0$ 覆盖掉移动的位置，再将 $1$ 插入，这一方法我们可以用位运算的方式实现。
先定义一个数组 $f$：
```cpp
const int f[4][4]= {{15,14,13,12},{11,10,9,8},{7,6,5,4},{3,2,1,0}};
```
这样会方便我们做位移之类的位运算操作。
~~另外利用该数组友情赠送 output 函数来输出状态（调试用）：~~
```cpp
void output(const ushort num)
{
for(int i=0;i<4;putchar('\n'),++i)
for(int j=0;j<4;++j)
putchar(((num>>f[i][j])&1)|'0');
}
```
用 $now$ 来表示当前要移动的状态，$x$ 和 $y$ 表示移动的位置，bool 值 $next$ 为真表示为上下移动，否则表示为左右移动。我们先用 $t1$ 和 $t2$ 储存移动前的位置和移动后的位置的状态（有无玩具）：
```cpp
const ushort t1=now&(1<<f[x][y]),t2=now&(1<<f[x+next][y+(!next)]);
```
然后覆盖的操作如下：
```cpp
now=now&(~t1)&(~t2);
```
然后插入操作如下：
```cpp
now=now|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y])；
```
两个操作合起来就是：
```cpp
(now&(~t1)&(~t2))|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y]);
```
我们只需要用一个 $\operatorname{move}$ 函数返回它的值即可:
```cpp
inline ushort move(const ushort now,const ushort x,const ushort y,const bool next)
{
const ushort t1=now&(1<<f[x][y]),t2=now&(1<<f[x+next][y+(!next)]);
return (now&(~t1)&(~t2))|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y]);
}
```
解决了状态的储存和处理后，就来思考如何求出最少移动次数吧！
不难想到，我们可以用广搜来找出这个最少移动次数。首先从初始状态开始找交换一次后的所有状态，再继续找，直到出现目标状态，再输出次数，另外还要筛掉已经出现过的状态。
用一个结构体数组来储存一种状态是否出现过且出现在第几次：
```cpp
struct st
{
ushort step;//储存出现次数
bool book;//储存是否出现过
}a[65536];
```
再来一些变量：
```cpp
queue<ushort> q;//队列，广搜必需，储存状态
ushort end;//储存目标状态
```
自己写个 $\operatorname{Push}$ 函数，其实就是在入队的时候做些特殊处理：
```cpp
inline bool Push(const ushort x,const ushort y,const bool next)//参数与 move 函数的后三个参数相同
{
ushort t=move(q.front(),x,y,next);//t 储存移动后状态
if(t==end)//如果移动后为目标状态
{
printf("%d",a[q.front()].step+1);//输出移动步数
return true;//返回真，表示已经搜索到了目标状态
}
if(a[t].book)//如果该状态没有被标记过（即没有搜索到过）
return false;//返回假，表示没有搜索到目标状态
q.push(t);//入队
a[t].step=a[q.front()].step+1;//移动次数比原来多1
a[t].book=true;//给该状态打上标记
return false;//返回假，表示没有搜索到目标状态
}
```
$\operatorname{bfs}$ （广搜）函数如下：
```cpp
inline void bfs()
{
q.push(input());//输入初始状态并入队
a[q.front()].book=true;//打上标记
end=input();//输入目标状态
if(q.front()==end)//判断初始状态与目标状态是否相同，有一个测试点就是这样
{
putchar('0');//毋庸置疑，移动次数肯定为0
return;
}
//广搜代码（应该不需要多讲了吧？）
do{
for(ushort i=0; i<4; ++i)
for(ushort j=0; j<3; ++j)
{
if(Push(i,j,false))
return;
else if(Push(j,i,true))
return;
}
q.pop();
}while(!q.empty());
}
```
这样，整个问题就解决了！完整代码如下：
```cpp
#include <queue>
#include <cstdio>
using namespace std;
typedef unsigned short ushort;
const int f[4][4]={{15,14,13,12},{11,10,9,8},{7,6,5,4},{3,2,1,0}};
inline bool getbool()//输入一个bool值（即 0 或 1）
{
char c;
do
c=getchar();
while(c!='1' && c!='0');
return c&1;
}
ushort input()
{
ushort num=0;
for(ushort i=0;i<16;++i)
num=(num<<1)|getbool();//num 左移一位后在后面插入一个bool值（0或1）
return num;
}
inline ushort move(const ushort now,const ushort x,const ushort y,const bool next)
{
const ushort t1=now&(1<<f[x][y]),t2=now&(1<<f[x+next][y+(!next)]);
return (now&(~t1)&(~t2))|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y]);
}
struct st
{
ushort step;//储存出现次数
bool book;//储存是否出现过
}a[65536];
queue<ushort> q;//队列，广搜必需，储存状态
ushort end;//储存目标状态
inline bool Push(const ushort x,const ushort y,const bool next)//参数与 move 函数的后三个参数相同
{
ushort t=move(q.front(),x,y,next);//t 储存移动后状态
if(t==end)//如果移动后为目标状态
{
printf("%d",a[q.front()].step+1);//输出移动步数
return true;//返回真，表示已经搜索到了目标状态
}
if(a[t].book)//如果该状态没有被标记过（即没有搜索到过）
return false;//返回假，表示没有搜索到目标状态
q.push(t);//入队
a[t].step=a[q.front()].step+1;//移动次数比原来多1
a[t].book=true;//给该状态打上标记
return false;//返回假，表示没有搜索到目标状态
}
inline void bfs()
{
q.push(input());//输入初始状态并入队
a[q.front()].book=true;//打上标记
end=input();//输入目标状态
if(q.front()==end)//判断初始状态与目标状态是否相同，有一个测试点就是这样
{
putchar('0');//毋庸置疑，移动次数肯定为0
return;
}
//广搜代码（应该不需要多讲了吧？）
do{
for(ushort i=0; i<4; ++i)
for(ushort j=0; j<3; ++j)
{
if(Push(i,j,false))
return;
else if(Push(j,i,true))
return;
}
q.pop();
}while(!q.empty());
}
int main()
{
bfs();
return 0;
}
```
还有一道类似的题目，A掉此题后也可以去做一做哦：
[P1225 黑白棋游戏](https://www.luogu.org/problemnew/show/P1225)