memset(board, -1, sizeof(board))
时间: 2023-06-10 16:04:50 浏览: 187
这是一个将数组board中的所有元素赋值为-1的操作。该函数是C语言标准库中的一个函数,函数原型为void *memset(void *s, int c, size_t n),其中s为要操作的数组指针,c为要赋的值,n为要赋值的元素个数。
相关问题
代码解读void bfs() { while (!q.empty()) { Node cur = q.top(); q.pop(); if (cur.box_x == end_x && cur.box_y == end_y) { best = cur.step; flag = true; break; } else for (int i = 0; i < 4; i++) { flag1 = false; memset(visit2, 0, sizeof(visit2)); int x = cur.box_x + dx[i]; int y = cur.box_y + dy[i]; if (x<1 || y<1 || x>n || y>m || board[x][y] == 1) continue; Node next; next.box_x = x; next.box_y = y; next.people_x = cur.box_x; next.people_y = cur.box_y; next.step = cur.step + 1; if (i == 0) if (cur.box_y - 1 > 0) if (board[cur.box_x][cur.box_y - 1] != 'S' && bfs2(cur.box_x, cur.box_y - 1, cur.box_x, cur.box_y, cur.people_x, cur.people_y) && !visit[x][y][cur.box_x][cur.box_y - 1]) { visit[x][y][cur.box_x][cur.box_y - 1] = 1; q.push(next); } if (i == 1) if (cur.box_y + 1 <= m) if (board[cur.box_x][cur.box_y + 1] != 'S' && bfs2(cur.box_x, cur.box_y + 1, cur.box_x, cur.box_y, cur.people_x, cur.people_y) && !visit[x][y][cur.box_x][cur.box_y + 1]) { visit[x][y][cur.box_x][cur.box_y + 1] = 1; q.push(next); } if (i == 2) if (cur.box_x - 1 > 0) if (board[cur.box_x - 1][cur.box_y] != 'S' && bfs2(cur.box_x - 1, cur.box_y, cur.box_x, cur.box_y, cur.people_x, cur.people_y) && !visit[x][y][cur.box_x - 1][cur.box_y]) { visit[x][y][cur.box_x - 1][cur.box_y] = 1; q.push(next); } if (i == 3) if (cur.box_x + 1 <= n) if (board[cur.box_x + 1][cur.box_y] != 'S' && bfs2(cur.box_x + 1, cur.box_y, cur.box_x, cur.box_y, cur.people_x, cur.people_y) && !visit[x][y][cur.box_x + 1][cur.box_y]) { visit[x][y][cur.box_x + 1][cur.box_y] = 1; q.push(next); } } } }
这段代码是一个广度优先搜索算法的实现,用于寻找最短路径。下面是代码的解读:
1. 首先,定义了一个名为 `bfs` 的函数,没有返回值(void)。
2. 在函数内部使用了一个 while 循环,判断队列 `q` 是否为空。
3. 在每次循环中,取出队首元素 `cur`,并将其从队列中移除。
4. 判断当前节点的箱子位置是否与目标位置相同,如果是,则更新最佳步数 `best`,设置标志位 `flag` 为 true,并跳出循环。
5. 如果当前节点的箱子位置与目标位置不同,则进行下一步的判断。
6. 使用一个 for 循环遍历四个方向(上、下、左、右)。
7. 首先,将一个名为 `flag1` 的布尔变量设为 false。
8. 使用 memset 函数将数组 `visit2` 的元素全部置为 0,该数组可能用于记录访问状态。
9. 根据当前节点 `cur` 的箱子位置和当前方向计算出下一步的位置 `x` 和 `y`。
10. 如果下一步的位置超出了边界或者是障碍物(`board[x][y] == 1`),则继续下一次循环。
11. 创建一个新的节点 `next`,并将下一步的位置赋值给 `next` 的箱子位置。
12. 将当前节点的人的位置赋值给 `next` 的人的位置。
13. 将当前节点的步数加1,并赋值给 `next` 的步数。
14. 根据当前方向的不同,进行不同的判断和操作:
- 如果当前方向是向左移动,并且箱子左边的位置不是墙壁(`board[cur.box_x][cur.box_y - 1] != 'S'`),并且调用了一个名为 `bfs2` 的函数,并且当前位置没有被访问过(`!visit[x][y][cur.box_x][cur.box_y - 1]`),则将 `next` 加入队列 `q` 中,并将对应的访问状态设置为已访问。
- 如果当前方向是向右移动,并且箱子右边的位置不是墙壁(`board[cur.box_x][cur.box_y + 1] != 'S'`),并且调用了一个名为 `bfs2` 的函数,并且当前位置没有被访问过(`!visit[x][y][cur.box_x][cur.box_y + 1]`),则将 `next` 加入队列 `q` 中,并将对应的访问状态设置为已访问。
- 如果当前方向是向上移动,并且箱子上边的位置不是墙壁(`board[cur.box_x - 1][cur.box_y] != 'S'`),并且调用了一个名为 `bfs2` 的函数,并且当前位置没有被访问过(`!visit[x][y][cur.box_x - 1][cur.box_y]`),则将 `next` 加入队列 `q` 中,并将对应的访问状态设置为已访问。
- 如果当前方向是向下移动,并且箱子下边的位置不是墙壁(`board[cur.box_x + 1][cur.box_y] != 'S'`),并且调用了一个名为 `bfs2` 的函数,并且当前位置没有被访问过(`!visit[x][y][cur.box_x + 1][cur.box_y]`),则将 `next` 加入队列 `q` 中,并将对应的访问状态设置为已访问。
15. 循环结束后,函数执行完毕。
此处代码片段并不完整,缺少了定义和初始化一些变量的部分,例如队列 `q`、数组 `dx` 和 `dy`、数组 `visit`、数组 `board` 等。同时,函数内部还调用了一个名为 `bfs2` 的函数,但在提供的代码中并没有给出其实现。因此,对于代码的完整性和准确性还需要进一步的了解。
问题描述:这个⼆进制迷锁具有⼀个⼤⼩为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) 表示从该节点到目标状态的启发式函数值。
具体实现过程如下:
```c
#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;
}
```
在运行时,程序会输出拨轮锁盘从起始状态到目标状态的所有步骤,以及总共需要的步数。
阅读全文
相关推荐















