原题传送门

蒟蒻还是一名在普及组题海奋战的蒟蒻，在别的OJ发现了这道好（ken）题，于是在网上博客学习了一番康托展开，手打了一个暴力BFS，结果出奇意料的拿了97分

想着自己2个小时的DEBUG拿不到AC硬是加了特判强过（蒟蒻行为，dalao求容忍度）

附上唯一一个WA(注意：是Wrong Answer)测试点:

input:836752104
wa:23
ac:21

蒟蒻调试了很久都没过，想着BFS的特性保证了第一个解必为最优，但它就是错了，没搞懂

代码附上，请求dalao帮助

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<string,int> psi;

int jc[9];
int vis[10000010];

string now;
int hash_goal;

const string goal = "123804765";

int ans = 2147483647;

queue<psi> q;

void init_jc(){
    int ji = 1;
    for(int i = 0;i<=8;i++){
        ji*=i+1;
        jc[i] = ji;
    }
}

int kt(string s){
    int sum = 0,len = s.size();
    int k;
    for(int i = 0;i<len;i++){
        k = s[i]-'0';
        sum+=k*jc[8-i];
    }
    return sum;
}

void bfs(){
    while(!q.empty()){
        psi n = q.front();
        string l = n.first;
        int ts = kt(l);
        q.pop();
        if(ts == hash_goal){
            ans = n.second;
            break;
        }
        if(vis[ts] != -1)continue;
        vis[ts] = n.second;
        int asd[4][4],nx,ny;
        for(int i = 1;i<=3;i++){
            for(int j = 1;j<=3;j++){
                asd[i][j] = l[(i-1)*3+j-1];
                if(asd[i][j] == '0')nx = i,ny = j;
            }
        }
        char ll[10] = "";
        if(nx != 1){
            swap(asd[nx][ny],asd[nx-1][ny]);
            for(int i = 1;i<=3;i++){
                for(int j = 1;j<=3;j++){
                    ll[(i-1)*3+j-1] = asd[i][j];    
                }
            }
            q.push({ll,n.second+1});
            swap(asd[nx][ny],asd[nx-1][ny]);
            memset(ll,0,sizeof(ll));
        }
        if(ny != 1){
            swap(asd[nx][ny],asd[nx][ny-1]);
            for(int i = 1;i<=3;i++){
                for(int j = 1;j<=3;j++){
                    ll[(i-1)*3+j-1] = asd[i][j];
                }
            }
            q.push({ll,n.second+1});
            swap(asd[nx][ny],asd[nx][ny-1]);
            memset(ll,0,sizeof(ll));    
        }
        if(nx != 3){
            swap(asd[nx][ny],asd[nx+1][ny]);
            for(int i = 1;i<=3;i++){
                for(int j = 1;j<=3;j++){
                    ll[(i-1)*3+j-1] = asd[i][j];
                }
            }

            q.push({ll,n.second+1});
            swap(asd[nx][ny],asd[nx+1][ny]);
            memset(ll,0,sizeof(ll));
        }
        if(ny != 3){
            swap(asd[nx][ny],asd[nx][ny+1]);
            for(int i = 1;i<=3;i++){
                for(int j = 1;j<=3;j++){
                    ll[(i-1)*3+j-1] = asd[i][j];
                }
            }

            q.push({ll,n.second+1});
            swap(asd[nx][ny],asd[nx][ny+1]);
            memset(ll,0,sizeof(ll));
        }
    }
}

int main(){
    init_jc();
    memset(vis,-1,sizeof(vis));
    cin>>now;
    hash_goal = kt(goal);
    q.push({now,0});
    bfs();
    cout<<ans;
    return 0;
}

（话说看到这道题标着个A*把我给吓得）

代码奇丑无比，中间那段人工解释一下：

把string(当前状态)变成二维数组，变换后再复原回string

if语句是边界判断

用时1.84s,内存40.89MB(空间强换时间的后果)

回复讨论