论坛 › 数据结构与算法 › 利用c语言实现用队列求解迷宫问题的最短路径

小彤酱 发表于 2023-10-15 18:52:45

利用c语言实现用队列求解迷宫问题的最短路径

利用c语言实现用队列求解迷宫问题的最短路径

陶远航 发表于 2023-10-15 18:53:44

在C语言中，我们可以使用广度优先搜索（BFS）算法和队列数据结构来求解迷宫问题的最短路径。以下是一个简单的实现：

首先，我们需要定义一个队列和一个节点：

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

#define MAXSIZE 100

typedef struct {
    int x;
    int y;
    int step;
} Node;

typedef struct {
    Node data;
    int front;
    int rear;
} Queue;

Queue* initQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = 0;
    q->rear = 0;
    return q;
}

void enqueue(Queue* q, Node node) {
    if ((q->rear + 1) % MAXSIZE == q->front) {
      return;
    }
    q->data = node;
    q->rear = (q->rear + 1) % MAXSIZE;
}

Node dequeue(Queue* q) {
    if (q->front == q->rear) {
      exit(0);
    }
    Node node = q->data;
    q->front = (q->front + 1) % MAXSIZE;
    return node;
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}


然后，我们可以使用广度优先搜索（BFS）算法来找到迷宫的最短路径：

#define N 5
#define M 5

int maze = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}
};

int visited = {0};

int direction = {
    {-1, 0}, // up
    {1, 0},// down
    {0, -1}, // left
    {0, 1}   // right
};

void BFS(int x, int y) {
    Queue* q = initQueue();
    Node start = {x, y, 0};
    enqueue(q, start);
    visited = 1;

    while (!isEmpty(q)) {
      Node cur = dequeue(q);
      if (cur.x == N - 1 && cur.y == M - 1) {
            printf(\"The shortest path is %d steps.\
\", cur.step);
            return;
      }

      for (int i = 0; i < 4; i++) {
            int newX = cur.x + direction[ i];
            int newY = cur.y + direction[ i];

            if (newX >= 0 && newX < N && newY >= 0 && newY < M && maze == 0 && visited == 0) {
                Node next = {newX, newY, cur.step + 1};
                enqueue(q, next);
                visited = 1;
            }
      }
    }

    printf(\"No path found.\
\");
}

int main() {
    BFS(0, 0);
    return 0;
}


在这个代码中，我们首先定义了一个迷宫和一个访问数组。然后，我们使用广度优先搜索（BFS）算法来找到迷宫的最短路径。我们从起点开始，然后探索每个方向，如果新的位置是可达的（即不是墙壁，并且没有被访问过），我们就将其添加到队列中，并更新步数和访问数组。当我们到达终点时，我们就找到了最短路径。如果队列为空，那么迷宫没有解决方案。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

isdkz 发表于 2023-10-15 18:54:19

这是一个经典的迷宫问题，可以使用广度优先搜索算法来解决。以下是使用队列实现的c语言代码：

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

#define ROW 10
#define COL 10

int maze = {
    {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 = {0}; // 标记是否已经访问过

int dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 上下左右四个方向

typedef struct {
    int x;
    int y;
    int step;
} Node; // 队列中的节点

typedef struct {
    Node data;
    int front;
    int rear;
} Queue; // 队列

Queue q;

void initQueue() {
    q.front = 0;
    q.rear = 0;
}

void enqueue(Node node) {
    q.data = node;
}

Node dequeue() {
    return q.data;
}

int isEmpty() {
    return q.front == q.rear;
}

int bfs(int startX, int startY, int endX, int endY) {
    initQueue();
    Node start = {startX, startY, 0};
    visited = 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];
            int ny = cur.y + dir[ i];
            if (nx >= 0 && nx < ROW && ny >= 0 && ny < COL && !visited && maze == 0) {
                visited = 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;
}


在上面的代码中，我们使用了一个队列来存储待访问的节点。首先将起点加入队列中，然后不断从队列中取出一个节点，遍历其四个相邻节点，如果相邻节点未被访问过且可通行，则加入队列中。当取出的节点为终点时，返回其步数即为最短路径长度。

Mike_python小 发表于 2023-10-15 18:56:31

求解迷宫问题的最短路径需要使用广度优先搜索算法和队列数据结构来实现。下面是用C语言实现的代码示例：


#include <stdio.h>
#include <stdbool.h>

#define MAX_ROW 10
#define MAX_COL 10

// 迷宫地图的大小
int row, col;

// 迷宫地图
int maze = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 1, 0, 0, 1, 0, 1},
    {1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 1, 0, 1},
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

// 定义坐标结构体
typedef struct {
    int x;
    int y;
} Coordinate;

// 定义队列结构体
typedef struct {
    Coordinate data;
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue *q, Coordinate elem) {
    q->data = elem;
    q->rear++;
}

// 出队
Coordinate dequeue(Queue *q) {
    Coordinate elem = q->data;
    q->front++;
    return elem;
}

// 广度优先搜索求解迷宫最短路径
bool breadthFirstSearch(Coordinate start, Coordinate end) {
    Queue queue;
    bool visited = {false}; // 记录每个位置是否已经访问过

    initQueue(&queue);
    enqueue(&queue, start);
    visited = true;

    int offsetX[] = {-1, 1, 0, 0}; // 上下左右的偏移量
    int offsetY[] = {0, 0, -1, 1};

    while (!isEmpty(&queue)) {
      Coordinate current = dequeue(&queue);

      if (current.x == end.x && current.y == end.y) {
            return true; // 找到了终点
      }

      // 遍历上下左右四个方向
      for (int i = 0; i < 4; i++) {
            int nextX = current.x + offsetX;
            int nextY = current.y + offsetY;

            // 判断是否可以移动到nextX, nextY，并且没有访问过
            if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col &&
                maze == 0 && !visited) {
                Coordinate next = {nextX, nextY};
                enqueue(&queue, next);
                visited = true;
            }
      }
    }

    return false; // 没有找到终点
}

int main() {
    row = 10;
    col = 10;

    Coordinate start = {1, 1};
    Coordinate end = {8, 8};

    bool found = breadthFirstSearch(start, end);

    if (found) {
      printf("找到了最短路径！\n");
    } else {
      printf("无法找到最短路径！\n");
    }

    return 0;
}


以上代码中，使用 Coordinate 结构体表示迷宫中的坐标，Queue 结构体表示队列。initQueue 函数用于初始化队列，isEmpty 函数用于判断队列是否为空，enqueue 函数用于入队，dequeue 函数用于出队。

breadthFirstSearch 函数使用广度优先搜索算法来求解迷宫的最短路径。首先初始化队列，并将起始坐标入队，并标记为已访问。然后进行循环，直到队列为空。在每一步循环中，出队一个坐标，判断是否为终点坐标，如果是则返回 true 表示找到了最短路径。否则，遍历当前位置上下左右四个方向，判断是否可以移动到相邻位置，并且没有访问过，如果满足条件，则将相邻位置入队，并标记为已访问。循环结束后，如果没有找到终点，则返回 false。

最后，在 main 函数中定义迷宫的大小、起点和终点，调用 breadthFirstSearch 函数进行求解，并输出结果。

希望这样的回答能帮助到你，如果还有其他问题，请继续提问。

球一个最佳答案谢谢啦！这对我非常重要！{:10_254:}{:10_254:}{:10_254:}

查看完整版本: 利用c语言实现用队列求解迷宫问题的最短路径