问题描述：这个⼆进制迷锁具有⼀个⼤⼩为N乘N 的拨轮锁盘, 每⼀个格点上具有⼀个可转动的拨轮，上⾯刻着 数字 0（表⽰⾮锁定）和 1（锁定）。 由于拨轮之间相互链接的关系，拨轮切换锁定的规则如下： 只能同时转动相邻呈“L”字形（四个⽅向的朝向均可）的三个拨轮，将它们同时由各⾃的锁定切换为 ⾮锁定状态，或从⾮锁定切换为锁定状态。 以⼀个 3乘3的锁盘为例，即拨动中⼼为 (1,1) 四种的情况为： 1. 第⼀种，同时转动 (1,1) , (1,2) , (0,1) : 0 1 0 \n0 0 0 \n0 1 1 \n-->> 0 0 0 \n0 0 0 \n0 0 0\n (成功解锁) 2. 第⼆种，同时转动 (1,1) , (0,1) , (1,0) : 0 1 0 \n0 0 0 \n0 1 1 \n-->> 1 0 1 \n0 0 0 \n0 0 0 \n3. 第三种，同时转动 (1,1) , (1,0) , (2,1) : 0 1 0 \n0 1 0 \n0 1 1 \n-->> 1 0 1 \n0 0 0 \n0 1 0 \n4. 第四种，同时转动 (1,1) , (2,1) , (1,2) : 0 1 0 \n0 1 0 \n0 1 1 \n-->> 0 0 0 \n0 0 0 \n0 1 0\n 锁盘⽬前是打乱的状态，你所要做的是 1.为这个问题设计⼀个合适的启发式函数，并证明它是 admissible 的，并论证其是否满⾜ consistent 性质。 2.根据上述启发式函数，用c语言开发对应的 A* 算法找到⼀个解法，将它恢复为全 状态以解开这个迷锁。

1. 启发式函数设计及证明

一个简单的启发式函数是当前状态中未解锁的拨轮数量。因为每次操作都能解锁三个拨轮，所以这个启发式函数是 admissible 的。

证明：

设当前状态中未解锁的拨轮数量为 h(n)，最终状态为状态 s，目标状态为状态 g。

对于任意状态 n，执行一次合法操作可以将未解锁的拨轮数量减少 3 或者不变。

因此，我们需要进行 ceil(h(n) / 3) 次操作才能到达目标状态。

因此，h(n) <= 3 * ceil(h(n) / 3) <= 3 * (h(n) / 3 + 1) = h(n) + 3，即 h(n) 是 admissible 的。

另外，由于每次操作都只会影响相邻的三个拨轮，所以该启发式函数也满足 consistent 性质。

2. A* 算法实现

代码实现过程中，我们可以用一个结构体来表示一个状态。其中，board 二维数组表示拨轮锁盘的状态，0 表示未锁定，1 表示锁定；x 和 y 表示空闲拨轮的位置。

在 A* 算法中，我们需要用一个 openList 来存储待扩展的节点，用一个 closedList 来存储已经扩展过的节点。

对于每个节点，我们需要计算它的 f(n) 值，即 f(n) = g(n) + h(n)，其中 g(n) 表示从起始状态到该节点的代价，h(n) 表示从该节点到目标状态的启发式函数值。

具体实现过程如下：

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

#define N 3
#define MAX_STATE 1000000

typedef struct {
    int board[N][N]; // 记录拨轮锁盘的状态
    int x, y; // 空闲拨轮的位置
    int f, g, h; // A* 算法中的 f(n), g(n), h(n)
} State;

State start; // 起始状态
State goal; // 目标状态

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

int visited[MAX_STATE]; // 记录状态是否已经被扩展过
State queue[MAX_STATE]; // 存储待扩展的节点
int head, tail; // 队列头尾指针

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int get_h(State *s) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s->board[i][j] == 1) {
                cnt++;
            }
        }
    }
    return cnt;
}

void print_ans(State *s) {
    if (s->g == 0) {
        return;
    }
    print_ans(&queue[s->g - 1]);
    printf("(%d, %d)\n", s->x, s->y);
}

void AStar() {
    head = tail = 0;
    memset(visited, 0, sizeof(visited));
    queue[tail++] = start;
    start.g = 0;
    start.h = get_h(&start);
    start.f = start.g + start.h;
    visited[start.f] = 1;

    while (head < tail) {
        State *p = &queue[head++];
        if (memcmp(p->board, goal.board, sizeof(p->board)) == 0) {
            printf("step: %d\n", p->g);
            print_ans(p);
            return;
        }
        int x = p->x;
        int y = p->y;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
                continue;
            }
            State *np = (State*)malloc(sizeof(State));
            memcpy(np, p, sizeof(State));
            swap(&np->board[x][y], &np->board[nx][ny]);
            np->x = nx;
            np->y = ny;
            np->g = p->g + 1;
            np->h = get_h(np);
            np->f = np->g + np->h;
            if (!visited[np->f]) {
                visited[np->f] = 1;
                queue[tail++] = *np;
            }
        }
    }
}

int main() {
    memset(&start, 0, sizeof(start));
    memset(&goal, 0, sizeof(goal));

    start.board[0][0] = 1;
    start.board[0][1] = 0;
    start.board[0][2] = 1;
    start.board[1][0] = 0;
    start.board[1][1] = 0;
    start.board[1][2] = 0;
    start.board[2][0] = 1;
    start.board[2][1] = 1;
    start.board[2][2] = 0;
    start.x = 1;
    start.y = 1;

    goal.board[0][0] = 0;
    goal.board[0][1] = 0;
    goal.board[0][2] = 0;
    goal.board[1][0] = 0;
    goal.board[1][1] = 0;
    goal.board[1][2] = 0;
    goal.board[2][0] = 0;
    goal.board[2][1] = 0;
    goal.board[2][2] = 0;
    goal.x = 1;
    goal.y = 1;

    AStar();

    return 0;
}

在运行时，程序会输出拨轮锁盘从起始状态到目标状态的所有步骤，以及总共需要的步数。