WA on #12

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;

string s, t = "123804765";
map <string, int> mp;
map <string, string> pre;
struct node
{
    string str;
    int pos;
    node() {}
    node(string _str, int _pos)
    {
        str = _str, pos = _pos;
    }
    friend bool operator < (node x, node y)
    {
        int sx = 0, sy = 0;
        for(int i = 0; i < 9; i++)
        {
            if(x.str[i] != t[i]) sx++;
            if(y.str[i] != t[i]) sy++;
        }
        return mp[x.str] + sx > mp[y.str] + sy;
    }
};
priority_queue <node> que;

void quepush(node p, int x)
{
    if(p.pos % 3 == 0 && x == -1) return;
    if(p.pos % 3 == 2 && x == 1) return;
    x = p.pos + x;
    if(x < 0 || x > 8) return;
    string tmp = p.str;
    swap(tmp[p.pos], tmp[x]);
    if(mp.find(tmp) == mp.end())
        mp[tmp] = mp[p.str] + 1, pre[tmp] = p.str, que.push(node(tmp, x));
    return;
}

void print(string s)
{
    if(pre.find(s) == pre.end()) return;
    print(pre[s]);
    cout << s << endl;
}

int main()
{
    cin >> s;
    int pos;
    for(int i = 0; i < 9; i++)
        if(s[i] == '0') pos = i;
    que.push(node(s, pos));
    mp[s] = 0;
    while(!que.empty())
    {
        node p = que.top();
        que.pop();
        if(p.str == t) break;
        quepush(p, -1);
        quepush(p, 1);
        quepush(p, -3);
        quepush(p, 3);
    }
    cout << mp[t] << endl;
    print(t);
    return 0;
}