题解 | #[JSOI2010]缓存交换#

循环次数较少，可以直接广搜

using namespace std;
string st,ed;
unordered_map<string, int> d;//记录每一个状态所需的交换次数
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs()
{
    queue<string> q;
    q.push(st);
    while(q.size())
    {
        string t=q.front();//从队列中取出一种状态
        q.pop();
        if(t==ed){cout<<d[ed];return;}//检查 是否已经满足目标状态
        for(int i=0;i<16;i++)//遍历当前状态的每一位
        {
            if(t[i]==ed[i])continue;//检查当前位的玩具是否符合要求
            int num=d[t];
            int x=i/4,y=i%4;//一维化二维
            for(int j=0;j<4;j++)
            {
               int sx=x+dx[j],sy=y+dy[j];
                if(sx<0||sx>=4||sy<0||sy>=4)continue;//边界判断
                swap(t[sx*4+sy],t[i]);//二维化一维并进行交换
                if(!d.count(t))//避免重复的情况放入
                {
                    d[t]=num+1;
                    q.push(t);
                }
//                  cout<<t<<endl;
                swap(t[sx*4+sy],t[i]);//恢复原状
            }
        }
    }
}
int main()
{
    string x;
    for(int i=0;i<4;i++)cin>>x,st+=x;
    for(int i=0;i<4;i++)cin>>x,ed+=x;
//     cout<<st<<endl<<ed;
    bfs();
}

代码是块砖，哪里需要哪里搬