Description

在一个 \(4 \times 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

Explanation

这道题就是一道暴力搜索题. 但是如果用上状态压缩, 跑这个类似最短路的问题会更快一些.

个人的代码风格趋向于更好看, 而不是更快, 所以花了差不多 36ms 才跑完 (我好菜啊), 前面好几整版的人全都是 0ms 水过此题......

话说如果用 DFS 的话这道题会被爆掉 (因为到了后面的状态总是会不断的每次 dist-2 缓慢地回溯, 所以注定要 T)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

#define rep(_var,_begin,_end) for (int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 70000;

int get_digit(int& __x, int __y) {
    return (__x >> __y) & 1; }
void set_digit(int& __x, int __y, int __z) {
    if (get_digit(__x, __y) == __z) return ;
    __x = __x ^ (1 << __y); return ; }
int swap_digit(int __x, int __y, int __z) {
    int d1 = get_digit(__x, __y),
        d2 = get_digit(__x, __z);
    set_digit(__x, __y, d2);
    set_digit(__x, __z, d1);
    return __x; }
int get_pos(int y, int x) {
    return (y - 1) * 4 + x - 1; }

int begin_state = 0,
    end_state = 0;

int dist[maxn];
int bfs(void)
{
    for (int i = 0; i < maxn; i++)
        dist[i] = -1;
    queue<int> que;
    dist[begin_state] = 0;
    que.push(begin_state);
    while (!que.empty()) {
        int in = que.front();
        que.pop();
        rep(i, 1, 4) rep(j, 1, 3) {
            int out = swap_digit(in, get_pos(i, j), get_pos(i, j + 1));
            if (dist[out] < 0 || dist[in] + 1 < dist[out])
                dist[out] = dist[in] + 1,
                que.push(out);
        }
        rep(i, 1, 3) rep(j, 1, 4) {
            int out = swap_digit(in, get_pos(i, j), get_pos(i + 1, j));
            if (dist[out] < 0 || dist[in] + 1 < dist[out])
                dist[out] = dist[in] + 1,
                que.push(out);
        }
        if (dist[end_state] > 0 && dist[in] > dist[end_state])
            break;
    }
    return dist[end_state];
}

int get_valid_number(void) { char ch = '\0';
    while (ch != '0' && ch != '1') ch = getchar();
    return ch - '0'; }

int main(int argc, char** argv)
{
    rep(i, 1, 4) rep(j, 1, 4) if (get_valid_number())
        set_digit(begin_state, get_pos(i, j), 1);
    rep(i, 1, 4) rep(j, 1, 4) if (get_valid_number())
        set_digit(end_state, get_pos(i, j), 1);
    printf("%d\n", bfs());
    return 0;
}