迷宫求解最短路径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 queue[ROW*COL][2] = {0};

// 队列头和尾指针
int front = 0, rear = 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 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");
}

// 广度优先搜索
void bfs() {
    // 先将起点加入队列
    queue[rear][0] = 0;
    queue[rear][1] = 0;
    rear++;
    visited[0][0] = 1;

    // 开始搜索
    while (front != rear) {
        // 出队
        int row = queue[front][0];
        int col = queue[front][1];
        front++;

        // 判断是否到达终点
        if (isEnd(row, col)) {
            // 打印路径
            printPath();
            return;
        }

        // 尝试向上走
        if (canMove(row-1, col)) {
            // 加入队列
            queue[rear][0] = row-1;
            queue[rear][1] = col;
            rear++;
            visited[row-1][col] = 1;
            pre[row-1][col][0] = row;
            pre[row-1][col][1] = col;
        }

        // 尝试向下走
        if (canMove(row+1, col)) {
            // 加入队列
            queue[rear][0] = row+1;
            queue[rear][1] = col;
            rear++;
            visited[row+1][col] = 1;
            pre[row+1][col][0] = row;
            pre[row+1][col][1] = col;
        }

        // 尝试向左走
        if (canMove(row, col-1)) {
            // 加入队列
            queue[rear][0] = row;
            queue[rear][1] = col-1;
            rear++;
            visited[row][col-1] = 1;
            pre[row][col-1][0] = row;
            pre[row][col-1][1] = col;
        }

        // 尝试向右走
        if (canMove(row, col+1)) {
            // 加入队列
            queue[rear][0] = row;
            queue[rear][1] = col+1;
            rear++;
            visited[row][col+1] = 1;
            pre[row][col+1][0] = row;
            pre[row][col+1][1] = col;
        }
    }

    // 没有找到路径
    printf("No path found!\n");
}

int main() {
    bfs();
    return 0;
}

该算法使用一个队列来存储待访问的位置，每次从队首取出一个位置进行访问，并将它周围可以访问的位置加入队列。在访问每个位置时，记录它的前一个位置，最后通过前一个位置数组来构造出最短路径。