记录编号	569260	评测结果	AAAAAAAAAA
题目名称	八数码问题	最终得分	100
用户昵称	zhk	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2022-02-27 15:38:02	内存使用	4.59 MiB

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


typedef pair<int,string> PIS;
#define x first
#define y second


int f(string state)
{
    int res=0;
    for(int i=0;i<state.size();i++)
        if(state[i]!='0')
        {
            int t=state[i]-'1';
            res+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    return res;
}

int bfs(string start)
{
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    
    string end="123804765";
    unordered_map<string,int> dist;
    priority_queue<PIS,vector<PIS>,greater<PIS>> heap;
    
    heap.push({0,start});
    dist[start]=0;
    while(heap.size())
    {
        PIS t=heap.top();
        heap.pop();
        
        string state=t.y;

        if(state==end) break;
        
        int step=dist[state];
        int x,y;
        for(int i=0;i<state.size();i++)
            if(state[i]=='0')
            {
                x=i/3;y=i%3;
                break;
            }
        string source=state;
        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) continue;
            swap(state[a*3+b],state[x*3+y]);
            
            if(dist.count(state)==0||dist[state]>dist[source]+1)
            {
                dist[state]=dist[source]+1;
                heap.push({dist[state]+f(state),state});
            }
            swap(state[a*3+b],state[x*3+y]);
        }
    }
    return dist[end];
}
int main()
{
	freopen("bama.in","r",stdin);
	freopen("bama.out","w",stdout);
    string start;
    cin>>start;
    cout<<bfs(start)<<endl;
    return 0;
}//A-Star