BFS+Cantor

#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int maxn = 362880;
int start[9];
int goal[9] = { 1,2,3,4,5,6,7,8,0 };
int factory[10];
bool visit[maxn];
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
char weizhi[4] = { 'u','l','d','r' };
struct node {
    int state[9];
    string step;
};
queue<node>q;
bool Cantor(int arr[9]) {
    long temp = 0;
    for (int i = 0; i < 9; i++) {
        int count = 0;
        for (int j = i + 1; j < 9; j++) {
            if (arr[j] > arr[i]) {
                count++;
            }
        }
        temp += count * factory[9 - 1 - i];
    }
    if (visit[temp] == false) {
        visit[temp] = true;
        return true;
    }
    else {
        return false;
    }
}
string bfs() {
    node head;
    memcpy(head.state, start, sizeof(head.state));
    head.step = "";
    q.push(head);
    Cantor(head.state);
    while (!q.empty()) {
        node temp = q.front();
        q.pop();
        int index = 0;
        for (int i = 0; i < 9; i++) {
            if (temp.state[i] == 0) {
                index = i;
                break;
            }
        }
        int x = index / 3;
        int y = index % 3;
        for (int i = 0; i < 4; i++) {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if (newx >= 0 && newx <= 2 && newy >= 0 && newy <= 2) {
                node newnode;
                newnode.step = temp.step + weizhi[i];
                //memcpy(&newnode, &temp, sizeof(struct node));
                memcpy(newnode.state, temp.state, sizeof(newnode.state));

                swap(newnode.state[index], newnode.state[newx*3+ newy]);
                if (memcmp(newnode.state, goal, sizeof(goal)) == 0) {
                    return newnode.step;
                }
                if (Cantor(newnode.state) == true) {
                    q.push(newnode);
                }
            }    
        }
    }
    return "unsolvable";
}
int main()
{
    char num;
    factory[0] = 1;
    for (int i = 1; i <=9; i++) {
        factory[i] = factory[i - 1]*i;
       // cout << factory[i] << endl;
    }
    for (int i = 0; i < 9; i++) {
        cin >> num;
        if (num == 'x'){
            start[i] = 0;
        }
        else {
            start[i] = num - '0';
        }
        //cout << start[i] << " ";
    }
    string s = bfs();
    cout << s;
}