迷宫求解最短路径c深度
时间: 2023-12-12 17:11:06 浏览: 77
使用深度优先搜索算法求解迷宫最短路径不是很常见,因为它并不保证能找到最短路径。不过,以下是使用深度优先搜索算法求解迷宫路径的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define ROW 6 // 迷宫行数
#define COL 6 // 迷宫列数
// 迷宫地图
int maze[ROW][COL] = {
{0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0}
};
// 记录迷宫中每个位置是否被访问过
int visited[ROW][COL] = {0};
// 记录每个位置的前一个位置
int pre[ROW][COL][2] = {0};
// 判断是否到达终点
int isEnd(int row, int col) {
return row == ROW-1 && col == COL-1;
}
// 判断某个位置是否可以走
int canMove(int row, int col) {
return row >= 0 && row < ROW && col >= 0 && col < COL && maze[row][col] == 0 && visited[row][col] == 0;
}
// 深度优先搜索
void dfs(int row, int col) {
// 标记为已访问
visited[row][col] = 1;
// 判断是否到达终点
if (isEnd(row, col)) {
return;
}
// 尝试向上走
if (canMove(row-1, col)) {
pre[row-1][col][0] = row;
pre[row-1][col][1] = col;
dfs(row-1, col);
}
// 尝试向下走
if (canMove(row+1, col)) {
pre[row+1][col][0] = row;
pre[row+1][col][1] = col;
dfs(row+1, col);
}
// 尝试向左走
if (canMove(row, col-1)) {
pre[row][col-1][0] = row;
pre[row][col-1][1] = col;
dfs(row, col-1);
}
// 尝试向右走
if (canMove(row, col+1)) {
pre[row][col+1][0] = row;
pre[row][col+1][1] = col;
dfs(row, col+1);
}
}
// 打印路径
void printPath() {
int row = ROW-1, col = COL-1;
printf("Path: (%d, %d)", row, col);
while (row != 0 || col != 0) {
int temp_row = row, temp_col = col;
row = pre[temp_row][temp_col][0];
col = pre[temp_row][temp_col][1];
printf(" -> (%d, %d)", row, col);
}
printf("\n");
}
int main() {
dfs(0, 0);
printPath();
return 0;
}
```
该算法使用递归来实现深度优先搜索。从起点开始,每次尝试向上、下、左、右四个方向走,如果某个方向可以走,则标记该位置为已访问,并递归地访问该位置。当到达终点时,递归回溯到上一个位置,继续尝试其他方向。在访问每个位置时,记录它的前一个位置,最后通过前一个位置数组来构造出路径。需要注意的是,该算法不保证能找到最短路径。
阅读全文