C语言 在迷宫中寻找最短路径问题
时间: 2024-03-08 12:45:54 浏览: 36
寻找迷宫中的最短路径可以使用广度优先搜索算法。下面是一个用C语言实现的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROW 5
#define COL 5
struct Node {
int row, col, dist;
};
bool isValid(int row, int col, char maze[][COL], bool visited[][COL]) {
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (maze[row][col] == '.' && !visited[row][col]);
}
void BFS(char maze[][COL], int startRow, int startCol, int destRow, int destCol) {
struct Node queue[ROW*COL];
bool visited[ROW][COL];
int front = 0, rear = 0;
int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
visited[i][j] = false;
}
}
visited[startRow][startCol] = true;
queue[rear++] = (struct Node){startRow, startCol, 0};
while (front < rear) {
struct Node cur = queue[front++];
if (cur.row == destRow && cur.col == destCol) {
printf("Shortest path is %d\n", cur.dist);
return;
}
for (int i = 0; i < 4; i++) {
int row = cur.row + rowNum[i];
int col = cur.col + colNum[i];
if (isValid(row, col, maze, visited)) {
visited[row][col] = true;
queue[rear++] = (struct Node){row, col, cur.dist+1};
}
}
}
printf("No path found!\n");
}
int main() {
char maze[][COL] = {
{'.', '.', '#', '.', '.'},
{'.', '.', '#', '.', '.'},
{'.', '.', '.', '.', '.'},
{'.', '#', '.', '#', '.'},
{'.', '.', '.', '#', '.'}
};
int startRow = 0, startCol = 0, destRow = 4, destCol = 4;
BFS(maze, startRow, startCol, destRow, destCol);
return 0;
}
```
在这个例子中,我们使用了一个结构体`Node`来表示位置以及从起点到该位置的距离。`isValid()`函数用于检查当前位置是否可以访问。`BFS()`函数实现了广度优先搜索算法,使用一个队列来存储访问过的位置。在搜索过程中,我们将当前位置周围的可访问位置加入队列中,并更新它们的距离。如果找到了目标位置,就输出最短路径距离。否则,输出“无法找到路径”。