|
发表于 2023-10-15 18:54:19
|
显示全部楼层
这是一个经典的迷宫问题,可以使用广度优先搜索算法来解决。以下是使用队列实现的c语言代码:
- #include <stdio.h>
- #include <stdlib.h>
- #define ROW 10
- #define COL 10
- int maze[ROW][COL] = {
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {0, 1, 0, 1, 1, 1, 0, 0, 0, 0},
- {0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
- }; // 迷宫地图
- int visited[ROW][COL] = {0}; // 标记是否已经访问过
- int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 上下左右四个方向
- typedef struct {
- int x;
- int y;
- int step;
- } Node; // 队列中的节点
- typedef struct {
- Node data[ROW * COL];
- int front;
- int rear;
- } Queue; // 队列
- Queue q;
- void initQueue() {
- q.front = 0;
- q.rear = 0;
- }
- void enqueue(Node node) {
- q.data[q.rear++] = node;
- }
- Node dequeue() {
- return q.data[q.front++];
- }
- int isEmpty() {
- return q.front == q.rear;
- }
- int bfs(int startX, int startY, int endX, int endY) {
- initQueue();
- Node start = {startX, startY, 0};
- visited[startX][startY] = 1;
- enqueue(start);
- while (!isEmpty()) {
- Node cur = dequeue();
- if (cur.x == endX && cur.y == endY) {
- return cur.step;
- }
- for (int i = 0; i < 4; i++) {
- int nx = cur.x + dir[ i][0];
- int ny = cur.y + dir[ i][1];
- if (nx >= 0 && nx < ROW && ny >= 0 && ny < COL && !visited[nx][ny] && maze[nx][ny] == 0) {
- visited[nx][ny] = 1;
- Node next = {nx, ny, cur.step + 1};
- enqueue(next);
- }
- }
- }
- return -1; // 无法到达终点
- }
- int main() {
- int startX = 1, startY = 1, endX = 8, endY = 8;
- int steps = bfs(startX, startY, endX, endY);
- printf("最短路径长度为:%d\n", steps);
- return 0;
- }
复制代码
在上面的代码中,我们使用了一个队列来存储待访问的节点。首先将起点加入队列中,然后不断从队列中取出一个节点,遍历其四个相邻节点,如果相邻节点未被访问过且可通行,则加入队列中。当取出的节点为终点时,返回其步数即为最短路径长度。 |
|