迷宫问题的广度优先的c语言代码

以下是一个使用广度优先算法解决迷宫问题的c语言代码示例：

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

#define ROW 6
#define COL 6

#define START_ROW 1
#define START_COL 1
#define END_ROW 4
#define END_COL 4

// 用于表示方向的枚举类型
enum DIR {
    UP,
    RIGHT,
    DOWN,
    LEFT
};

// 用于表示迷宫中的每个格子的状态的枚举类型
enum STATUS {
    SPACE,
    WALL,
    START,
    END,
    ROUTE
};

// 迷宫数组
int maze[ROW][COL] = {
    {1,1,1,1,1,1},
    {1,0,0,0,0,1},
    {1,0,1,0,1,1},
    {1,0,1,0,0,1},
    {1,0,1,1,0,1},
    {1,1,1,1,1,1}
};

// 标志数组，用于标记某个格子是否已经被访问过
int visited[ROW][COL];

// 用于表示从某个格子出发向某个方向前进的时候需要修改的行数和列数
int deltaRow[4] = {-1, 0, 1, 0};
int deltaCol[4] = {0, 1, 0, -1};

// 从起点走到终点的路径
int route[ROW][COL];

// 判断某个格子是否是合法的格子（即是否在迷宫内，是否是墙壁等）
int is_valid(int r, int c)
{
    if (r < 0 || r >= ROW || c < 0 || c >= COL || maze[r][c] == WALL)
    {
        return 0;
    }

    return 1;
}

// 广度优先搜索
// 返回：如果能够找到一条从起点到终点的路径，返回1，反之返回0
int bfs()
{
    // 定义搜索队列，用于存储等待访问的格子
    int queue[ROW * COL][2];
    int head = 0;
    int tail = 0;

    // 将起点加入搜索队列
    queue[tail][0] = START_ROW;
    queue[tail][1] = START_COL;
    tail++;

    // 标记起点已经被访问过
    visited[START_ROW][START_COL] = 1;

    // 广度优先遍历搜索队列中的格子
    while (head != tail)
    {
        // 取出队首格子
        int r = queue[head][0];
        int c = queue[head][1];
        head++;

        // 如果已经找到终点，返回1
        if (r == END_ROW && c == END_COL)
        {
            return 1;
        }

        // 枚举从当前格子出发可以到达的所有格子
        for (int i = 0; i < 4; i++)
        {
            int new_r = r + deltaRow[i];
            int new_c = c + deltaCol[i];

            // 如果新格子是合法的格子且没有被访问过
            if (is_valid(new_r, new_c) && !visited[new_r][new_c])
            {
                // 将新格子加入搜索队列
                queue[tail][0] = new_r;
                queue[tail][1] = new_c;
                tail++;

                // 标记新格子已经被访问过
                visited[new_r][new_c] = 1;

                // 记录新格子是从哪个格子转移过来的
                route[new_r][new_c] = r * COL + c;
            }
        }
    }

    // 没有找到起点到终点的路径，返回0
    return 0;
}

// 输出路径
void print_route()
{
    int r = END_ROW;
    int c = END_COL;

    while (r != START_ROW || c != START_COL)
    {
        // 将路径上的格子标记为ROUTE
        maze[r][c] = ROUTE;

        // 计算路径上的下一个格子的行列数
        int rc = route[r][c];
        r = rc / COL;
        c = rc % COL;
    }

    // 将起点和终点也标记为ROUTE
    maze[START_ROW][START_COL] = ROUTE;
    maze[END_ROW][END_COL] = ROUTE;

    // 输出标记后的迷宫
    for (int r = 0; r < ROW; r++)
    {
        for (int c = 0; c < COL; c++)
        {
            switch (maze[r][c])
            {
                case SPACE:
                    printf(" ");
                    break;
                case WALL:
                    printf("#");
                    break;
                case START:
                case END:
                    printf("X");
                    break;
                case ROUTE:
                    printf("*");
                    break;
                default:
                    break;
            }
        }

        printf("\n");
    }
}

int main()
{
    memset(route, -1, sizeof(route));
    if (bfs())
    {
        print_route();
    }
    else
    {
        printf("no route found.\n");
    }

    return 0;
}