题解 P4289 【[HAOI2008]移动玩具】

Createsj · 2018-11-09 13:17:29 · 题解

博客食用效果更佳~

让我们先来看看题目：

题目描述

在一个 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。

typedef unsigned short ushort;

接下来我们来写输入函数用于输入起始和目标状态：

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;
}

接下来就是解决移动玩具的问题了。

比如样例的初始状态为：

按照我给出的输入函数，初始状态被保存为二进制数

我们想要第 0 行第 0 列的玩具向下移动，即使初始状态变为：

保存为

很显然，这相当于交换两位数。

可以想到，我们可以先用 0 覆盖掉移动的位置，再将 1 插入，这一方法我们可以用位运算的方式实现。

先定义一个数组 f：

const int f[4][4]= {{15,14,13,12},{11,10,9,8},{7,6,5,4},{3,2,1,0}};

这样会方便我们做位移之类的位运算操作。

另外利用该数组友情赠送 output 函数来输出状态（调试用）：

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 储存移动前的位置和移动后的位置的状态（有无玩具）：

const ushort t1=now&(1<<f[x][y]),t2=now&(1<<f[x+next][y+(!next)]);

然后覆盖的操作如下：

now=now&(~t1)&(~t2);

然后插入操作如下：

now=now|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y])；

两个操作合起来就是：

(now&(~t1)&(~t2))|(t1>>f[x][y]<<f[x+next][y+(!next)])|(t2>>f[x+next][y+(!next)]<<f[x][y]);

我们只需要用一个 \operatorname{move} 函数返回它的值即可:

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;//储存目标状态

自己写个 \operatorname{Push} 函数，其实就是在入队的时候做些特殊处理：

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;//返回假，表示没有搜索到目标状态
}