信息学奥赛一本通T1453：移动玩具

【题目描述】

在一个 4×4 的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到目标状态。

【输入】

前四行表示玩具的初始状态，每行 4 个数字 1 或 0，1 表示方格中放置了玩具，0 表示没有放置玩具。

接着是一个空行。

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

【输出】

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

【输入样例】

1111

0000
1110
0010

1010
0101
1010
0101

【输出样例】

4

思路：与 棋盘游戏（信息学奥赛一本通-T1451）是同一个题

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;}
LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;}
LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; }
LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-6;
const int MOD = 1000000000+7;
const int N = 1000+5;
const int dx[] = {0,0,-1,1,1,-1,1,1};
const int dy[] = {1,-1,0,0,-1,1,-1,1};
using namespace std;

struct Node {
    int val;
    int step;
    Node() {}
    Node(int val, int step) : val(val), step(step) {}
};
int vis[65536 + 10];
void BFS(Node st, Node ed) {
    memset(vis, 0, sizeof(vis));
    queue<Node> Q;
    Q.push(st);
    while (!Q.empty()) {
        Node now = Q.front();
        Q.pop();
        if (now.val == ed.val) {
            cout << now.step << endl;
            return;
        }

        int val = now.val;
        int step = now.step;
        for (int i = 15; i >= 0; i--) { //从高到低枚举每一位
            int x = (15 - i) / 4, y = (15 - i) % 4; //横纵坐标
            int nowPos = 1 << i; //当前位置代表权值
            int rightPos = 1 << (i - 1); //当前位置右方位置代表权值
            int downPos = 1 << (i - 4);  //当前位置下方位置代表权值
            if (y < 3 && ((val & nowPos) != (val & rightPos))) { //向右交换
                int nextVal = val ^ nowPos ^ rightPos; //交换后的状态
                if (!vis[nextVal]) {
                    vis[nextVal] = true;
                    Q.push(Node(nextVal, step + 1));
                }
            }
            if (x < 3 && ((val & nowPos) != (val & downPos))) { //向下交换
                int nextVal = val ^ nowPos ^ downPos; //交换后的状态
                if (!vis[nextVal]) {
                    vis[nextVal] = true;
                    Q.push(Node(nextVal, step + 1));
                }
            }
        }
    }
}
int main() {
    char ch;
    int st = 0, ed = 0;
    for (int i = 15; i >= 0; i--) {
        cin >> ch;
        if (ch == '1')
            st += 1 << i;
    }
    for (int i = 15; i >= 0; i--) {
        cin >> ch;
        if (ch == '1')
            ed += 1 << i;
    }
    if (st == ed)
        printf("0\n");
    else
        BFS(Node(st, 0), Node(ed, 0));
    return 0;
}

信息学奥赛一本通T1453：深搜的剪枝技巧 移动玩具 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 移动玩具