题目描述

详细题解

样例

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
using namespace std;
unordered_map<string,int> d;//string 表示状态，int 表示距离
queue<string> q;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int bfs(string start)
{
    string end="12345678x";
    q.push(start);
    d[start]=0;//初始字符串到初始字符串的距离为零
    while(q.size())
    {
        auto t=q.front();//将最先入队的字符串取出
        q.pop();
        int dist=d[t];
        if(t==end) return dist;
        int k=t.find('x');//查询x在t字符串中的位置
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                //交换a,b
                swap(t[k],t[a*3+b]);
                //如果当前状态是第一次遍历，记录距离，入队
                if(!d.count(t))//如果t不在d中
                {
                    d[t]=dist+1;//将t写入字符串且更新位置
                    q.push(t);//新状态写入队列
                }
                //恢复
                swap(t[k],t[a*3+b]);
            }
        }

    }
    return -1;
}
int main()
{
    string start;
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        start+=c;
    }
    cout<<bfs(start)<<endl;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla