分析

上面是一个简单示例。

难点有：

1. 每走一步是一个状态，这个状态怎么表示？用string记忆状态
2. 如何关联状态和当前的距离？map,或者hash映射为坐标
3. 转移条件如何描述？从一维转为二维坐标，交换字符

手写Hash 1142ms

#include<bits/stdc++.h>
using namespace std;

const int M=1e7+12;//调节M避免冲突
int d[M];
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};


int hashToIdx(string s)
{
    int seed = 313; // 31 131 1313 13131 131313 etc..
    int hash = 0;

    const char* str=s.c_str();
    while (*str)
        hash = hash * seed + (*str++);

    return (hash & 0x7FFFFFFF)%M;
}

bool check(int nx,int ny){
    return nx>=0&&nx<3&&ny>=0&&ny<3;
}

int bfs(string state)
{
    queue<string> q;
    q.push(state);  
    d[hashToIdx(state)]=0;

    while(q.size())
    {
        string now = q.front();
        q.pop(); 
        int nowi = hashToIdx(now);
        int now_dist=d[nowi];


        if(now == "12345678x") return now_dist;


        int k=now.find('x');
        int x=k/3,y=k%3;//转换为二维
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(check(nx,ny))
            {
                swap(now[nx*3+ny],now[k]);//这一步之后，now已经变成了下一个状态
                int nxti=hashToIdx(now);
                if(!d[nxti])//d数组初始化时0，是0代表该结点 未被访问过 
                {
                    d[nxti]=now_dist+1;
                    q.push(now);  
                } 
                swap(now[nx*3+ny],now[k]);//恢复现场
            }

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

    cout << bfs(state) << endl;
    return 0;
}

3359ms 使用map映射有state --->dist

#include<bits/stdc++.h>
using namespace std;



int bfs(string state)
{

    queue<string> q;//队列存放状态
    unordered_map<string,int>d;

    q.push(state); 
    d[state]=0;



    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};

    while(q.size())
    {
        string t=q.front();
        q.pop();
        if(t=="12345678x") return d[t];

        int distance=d[t];

        int k=t.find('x');
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(t[a*3+b],t[k]);//t跳跃为下一状态
                if(!d.count(t))
                {
                    d[t]=distance+1;
                    q.push(t);  
                } 
                swap(t[a*3+b],t[k]);//恢复现场
            }

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

    cout << bfs(state) << endl;

    return 0;
}