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

Question

题目链接： 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;
}

Answer 1

是超时吗