八数码问题c语言代码最佳优先

以下是使用A*搜索算法解决八数码问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1000000

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char dir[4] = {'d', 'r', 'u', 'l'};
int vis[MAXN], pre[MAXN], op[MAXN];
int fact[9], digits[9];

struct node {
    int puzzle[3][3];
    int step, f;
    int hashvalue;
}start, goal, node;

void init_lookup_table() {
    fact[0] = 1;
    for (int i = 1; i < 9; i++) {
        fact[i] = fact[i-1] * i;
    }
}

int get_hashvalue(int puzzle[][3]) {
    int code = 0;
    for (int i = 0; i < 9; i++) {
        int cnt = 0;
        for (int j = i+1; j < 9; j++) {
            if (puzzle[j/3][j%3] < puzzle[i/3][i%3]) {
                cnt++;
            }
        }
        code += fact[8-i] * cnt;
    }
    return code;
}

int bfs() {
    init_lookup_table();
    memset(vis, 0, sizeof(vis));
    int front = 0, rear = 1;
    memcpy(node.puzzle, start.puzzle, sizeof(node.puzzle));
    node.step = node.f = 0;
    node.hashvalue = get_hashvalue(node.puzzle);
    vis[node.hashvalue] = 1;
    while (front < rear) {
        memcpy(node.puzzle, op[front] ? goal.puzzle : start.puzzle, sizeof(node.puzzle));
        node.step = pre[front] + 1;
        for (int i = 0; i < 9; i++) {
            if (!node.puzzle[i/3][i%3]) {
                int x = i/3, y = i%3;
                for (int j = 0; j < 4; j++) {
                    int newx = x + dx[j];
                    int newy = y + dy[j];
                    if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
                        memcpy(&node.puzzle[x][y], &node.puzzle[newx][newy], sizeof(int));
                        memcpy(&node.puzzle[newx][newy], &(digits[0]), sizeof(int));
                        node.hashvalue = get_hashvalue(node.puzzle);
                        if (!vis[node.hashvalue]) {
                            memcpy(op+rear, op+front, sizeof(op[front]));
                            op[rear-1] = j;
                            memcpy(pre+rear, pre+front, sizeof(pre[front]));
                            pre[rear++] = node.step;
                            memcpy(vis+node.hashvalue, &rear, sizeof(int));
                            node.f = node.step + get_hashvalue(node.puzzle);
                            if (node.hashvalue == goal.hashvalue) {
                                return rear-1;
                            }
                        }
                        memcpy(&node.puzzle[newx][newy], &node.puzzle[x][y], sizeof(int));
                        memcpy(&node.puzzle[x][y], &(digits[0]), sizeof(int));
                    }
                }
                break;
            }
        }
        front++;
    }
    return -1;
}

int main() {
    for (int i = 0; i < 9; i++) {
        scanf("%d", digits+i);
        if (!digits[i]) {
            digits[i] = 9;
        }
    }
    for (int i = 0; i < 9; i++) {
        start.puzzle[i/3][i%3] = digits[i];
    }
    for (int i = 0; i < 9; i++) {
        scanf("%d", digits+i);
        if (!digits[i]) {
            digits[i] = 9;
        }
    }
    for (int i = 0; i < 9; i++) {
        goal.puzzle[i/3][i%3] = digits[i];
    }
    start.hashvalue = get_hashvalue(start.puzzle);
    goal.hashvalue = get_hashvalue(goal.puzzle);
    int rear = bfs();
    if (rear == -1) {
        printf("unsolvable\n");
    } else {
        printf("%d\n", pre[rear]);
        for (int i = rear-1; i >= 0; i--) {
            printf("%c", dir[op[i]]);
        }
        printf("\n");
    }
    return 0;
}