八数码问题,提交不成功,不知道哪里错了

题目链接: 1077 -- Eight http://poj.org/problem?id=1077
题目要求:输入一个字符串(表示九宫格状态),要求输出其变成标准形式的移动步骤(u表示上,d表示下,l表示左,r表示右),无解则输出unsolvable

样例过了,也用了逆序数判无解的情况(也测试过可以),提交就出错了,但是就是不知道哪里出错了,看了好几遍自己的代码了,也不知道错在哪里,希望大家能帮我看看,感谢🙇‍。 代码如下

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

map<string,int>Map;
pair<string,string>p;
queue<string> q;

string str;
string mb = "12345678x";

bool check(string s){ //判断是否为目标
    for(int i = 0; i < 9; i++){
        if(s[i] != mb[i])return false;
    }
    return true;
}

bool unsolvable(string s){ //判断是否有解函数
    int t = 0;
    for(int i = 0; i < s.length() - 1; i++){
        for(int j = i + 1; j < s.length(); j++){
            if(s[i] == 'x' || s[j] == 'x')continue;
            int a = s[i] - '0';
            int b = s[j] - '0';
            if(a > b)t++;
        }
    }
    //cout << "t = " << t << endl;
    if(t&1)return false;
    return true;
}

bool bfs(string s){
    string s1,s2;
    q.push(s);
    Map.insert(pair<string,int>(s,66));
    while(!q.empty()){
        s1 = q.front(); q.pop();
        if(!unsolvable(s1))return false; //判断是有解
        if(check(s1)){
            string str1,str2;
            char str3[1000];
            int a = Map.find(s1)->second,b = 0;
            str1 = Map.find(s1)->first;
            while(a != 66 && a != 0){  //下面是通过map保存的字符串逆向回去,打印移动路径
                int xx;
                for(int i = 0; i < 9; i++){
                    if(str1[i] == 'x')xx = i;
                }
                if(a == -3){
                    str3[b++] = 'u';
                    str2 = str1;
                    str2[xx] = str1[xx+3];
                    str2[xx+3] = str1[xx];
                }
                if(a == -1){
                    str3[b++] = 'l';
                    str2 = str1;
                    str2[xx] = str1[xx+1];
                    str2[xx+1] = str1[xx];
                }
                if(a == 3){
                    str3[b++] = 'd';
                    str2 = str1;
                    str2[xx] = str1[xx-3];
                    str2[xx-3] = str1[xx];
                }
                if(a == 1){
                    str3[b++] = 'r';
                    str2 = str1;
                    str2[xx] = str1[xx-1];
                    str2[xx-1] = str1[xx];
                }
                str1 = str2;
                a = Map.find(str2)->second;
            }
            for(int i = b - 1; i >= 0; i--)cout << str3[i];
            return true;
        }
        int x;
        for(int i = 0; i < 9; i++){  //定位x的位置 (x分四个方向进行移动,用一维数组模拟)
            if(s1[i] == 'x')x = i;
        }
        //上
        if(x - 3 >= 0){
            s2 = s1;
            s2[x-3] = s1[x];
            s2[x] = s1[x-3];
            if(Map.find(s2) == Map.end()){
                Map.insert(pair<string,int>(s2,-3));
                q.push(s2);
            }
        }
        //左
        if(x - 1 >= 0 && (x % 3) != 0){  //用一维数组模拟二维,(在二维中)当x在某一行的最左边就不能往左移了,下面类似
            s2 = s1;
            s2[x-1] = s1[x];
            s2[x] = s1[x-1];
            if(Map.find(s2) == Map.end()){
                Map.insert(pair<string,int>(s2,-1));
                q.push(s2);
            }
        }
            //下
        if(x + 3 < 9){
            s2 = s1;
            s2[x+3] = s1[x];
            s2[x] = s1[x+3];
            if(Map.find(s2) == Map.end()){
                Map.insert(pair<string,int>(s2,3));
                q.push(s2);
            }
        }
        //右
        if(x + 1 < 9 && ((x + 1) % 3) != 0){
            s2 = s1;
            s2[x+1] = s1[x];
            s2[x] = s1[x+1];
            if(Map.find(s2) == Map.end()){
                Map.insert(pair<string,int>(s2,1));
                q.push(s2);
            }
        }
    }
    return false;
}


int main(){
    char c[9];
    for(int i = 0; i < 9; i++)cin >> c[i];
    str = c;
    if(!bfs(str))cout << "unsolvable" << endl;
    return 0;
}

是超时吗

定义估价函数h():为每个数或空格的位置 到 最终状态中所在位置 的 曼哈顿距离 的 总和。

把状态压成一个九进制数,便于存储和判重。

然后记录方案可以记录一下此次的操作和上一次的状态,具体见代码。

map比哈希快

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<algorithm>
#define R register int
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1},end=54480996;
const int py[]={0,1,2,0,1,2,0,1},px[]={0,0,0,1,1,1,2,2};
const char op[4]={'u','r','d','l'};
using namespace std;
inline int g() {
    R ret=0; register char ch; while(!isdigit(ch=getchar()));
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret;
}
struct node{ int sta,g,h; node() {}
    node(int ss,int gg,int hh) {sta=ss,g=gg,h=hh;}
    bool operator <(const node& y) const {return g+h>y.g+y.h;}
}; int a[3][3];
map<int,int> d,pre,dir;
priority_queue<node> q;
inline bool ckpos(int x,int y) {return x<0||x>2||y<0||y>2;}
inline int calc(int p[3][3]) { R ret=0;
    for(R i=0;i<3;++i) for(R j=0;j<3;++j) ret=ret*9+p[i][j]; return ret;
}
inline pair<int,int> recalc(int vl,int p[3][3]) { R x,y;
    for(R i=2;i>=0;--i) for(R j=2;j>=0;--j) {
        p[i][j]=vl%9,vl/=9; if(p[i][j]==0) x=i,y=j;
    } return make_pair(x,y);
}
inline int h(int p[3][3]) { R ret=0;
    for(R i=0;i<3;++i) for(R j=0;j<3;++j) {
        if(p[i][j]==0) continue;
        ret+=abs(i-px[p[i][j]-1])+abs(j-py[p[i][j]-1]);
    } return ret;
}
inline int Astar() {
    d.clear(),pre.clear(),dir.clear();
    while(q.size()) q.pop(); R st=calc(a); d[st]=0;
    q.push(node(st,0,h(a)));
    while(q.size()) {
        node u=q.top(); R crt=q.top().sta; q.pop();
        if(crt==end) return u.g;
        R a[3][3]; register pair<int,int> blk=recalc(crt,a); R x=blk.first,y=blk.second;
        for(R i=0;i<4;++i) { R xx=x+dx[i],yy=y+dy[i];
            if(ckpos(xx,yy)) continue; swap(a[x][y],a[xx][yy]);
            R nxt=calc(a); if(d.find(nxt)==d.end()||d[nxt]>d[crt]+1) 
                d[nxt]=d[crt]+1,pre[nxt]=crt,dir[nxt]=i,q.push(node(nxt,d[nxt],h(a)));//此处存了nxt的上一个状态和如何操作
            swap(a[xx][yy],a[x][y]);
        }
    } return -1;
}
inline void print(int s) {
    if(pre.find(s)==pre.end()) return;
    print(pre[s]); putchar(op[dir[s]]);
}
signed main() {
    for(R i=0;i<3;++i) for(R j=0;j<3;++j) { register char ch;
        while(!isdigit(ch=getchar())&&ch!='x');
        if(ch=='x') a[i][j]=0;
        else a[i][j]=ch^48;
    } R ans=Astar(); if(ans==-1) printf("unsolvable"),putchar('\n'); else print(end);
}