八数码

#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#define maxn 3
using namespace std;

int aim = 0;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct Node
{
    int x, y;
    int step = 0;
    // int status;
    char status[maxn][maxn];
};
Node s;

bool judge(const Node &a)
{
    if (a.x<0 || a.x>2 || a.y<0 || a.y>2)
        return false;
    return true;
}

int matrix2int(char status[maxn][maxn])
{    //得到每一种状态的标识
    int ans = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            ans = ans*10+status[i][j]-'0';
    return ans;
}

void copyM(char a[maxn][maxn], char b[maxn][maxn])
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            b[i][j] = a[i][j];
}

int bfs()
{
    queue<Node> q;
    map<int, int> hashMp;
    // Node next;
    q.push(s);
    int key = matrix2int(s.status);
    if (key==aim)
        return 1;
    ++hashMp[key];
    while (!q.empty())
    {
        s = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            Node next = s;
            next.x = s.x+dx[i];
            next.y = s.y+dy[i];
            next.step = s.step+1;
            if (judge(next))
            {
                // copyM(s.status, next.status);
                swap(next.status[next.x][next.y], next.status[s.x][s.y]);
                int key = matrix2int(next.status);
                if (key == aim)
                    return next.step;
                if (hashMp[key]==0)
                {
                    q.push(next);
                    hashMp[key]++;
                }
            }
        }
    }
    return -1;
}

int main()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%c", &s.status[i][j]);
            getchar();  //吃空格和回车
            if (s.status[i][j]=='x')    //把x换成0字符
            {
                s.x = i, s.y = j;
                s.status[i][j]='0';
            }
               
        }
    }
    aim=123456780;

    printf("%d\n", bfs());
    return 0;
}