链接：https://ac.nowcoder.com/acm/problem/19975
来源：牛客网

题目描述

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

输入描述: 

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。
接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

输出描述: 

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

思路

先看数据范围：4*4，考虑直接BFS搜索+剪枝
先确定如何搜索
1.搜索结束条件：当前队列里的字符串与目标状态的字符串相等
2.搜索方法：遍历当前字符串的每一位，如果与目标状态相同则跳过，如果与目标状态不同，则取出这个位置的字符，并对其进行四个方向的探索，如果没有到边界就可以存入队列
（这里可能会有疑惑：1.不是只能对一进行移动吗？因为对1移动和对0移动在交换上是等价的；2.不用判断1碰到1的情况吗？因为就算1碰到1也可以交换，反正1和1交换过后的字符串不变）
3.是否要回溯：要，因为同一个位置可能会被遍历多次
4.防止TLE：因为程序不对其进行限定的话，会出现死循环的情况，所以开一个map进行剪枝，如果当前的字符串在map中出现过，说明这个字符串的状态之前已经存在过，就没必要再对其进行操作了

P.S.:推荐一道有点类似的题（剪枝策略类似）：1015-八数码_2021秋季算法入门班第六章习题：搜索与搜索剪枝

代码如下
#include<bits/stdc++.h>
using namespace std;
string st,ed,tmp;
struct node{
    int step;
    string s;
    bool operator<(const node &n)const{
        return step>n.step;
    }
};
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int ans=0;
unordered_map<string,int>mp;
priority_queue<node>q;
void BFS(){
    while(!q.empty()){
        node t=q.top();
        q.pop();
        if(ed==t.s){
            ans=t.step;
            return;
        }
        for(int i=0;i<16;i++){
            if(t.s[i]==ed[i]) continue;
            int x=i/4,y=i%4;
            for(int j=0;j<4;j++){
                int xt=x+dir[j][0],yt=y+dir[j][1]; //获取字符串在4*4图中的坐标
                if(xt<0 || xt>=4 || yt<0 || yt>=4) continue;
                swap(t.s[i],t.s[xt*4+yt]);
                if(!mp[t.s]){ //剪枝：防止死循环导致的TLE
                    mp[t.s]=1;
                    q.push(node{t.step+1,t.s}); //满足条件，存入队列
                }
                swap(t.s[i],t.s[xt*4+yt]); //回溯
            }
        }
    }
}
int main(){
    for(int i=0;i<4;i++){
        cin>>tmp;
        st+=tmp;
    }
    for(int i=0;i<4;i++){
        cin>>tmp;
        ed+=tmp;
    }
    q.push(node{0,st});
    BFS();
    cout<<ans<<endl;
    return 0;
}