C语言编写程序之哨兵的重任-QQ沐编程

题目描述

关键词:路径搜索,深度优先(DFS),广度优先(BFS)

使一台机器人能自主的在场上快速移动是导航组的主要任务。由于比赛场地有较多的障碍物，所以在驱使机器人运动之前，我们需要为机器人规划出一条安全可行的路径。现在以一个二维数组表示一张地图，数组中的元素只有1和0两种状态，其中1表示该位置被障碍物占用，0表示该位置没有障碍物。请编写一段代码，自行输入机器人在场中的起点位置和要到达的终点位置，输出机器人安全能到达终点的可行路线。

注:①机器人目前只能进行前后左右的运动，无法斜着走;

②请输出机器人到达终点需要的行进步数，越少越好;

③为统一评分，初始地图已给出，请直接在原程序上进行路径规划

源代码

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

#define ROWS 8
#define COLS 8

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

// 定义队列节点结构体
typedef struct {
    Coordinate coord;
    int distance;
} QueueNode;

// 定义队列结构体
typedef struct {
    QueueNode* nodes;
    int front;
    int rear;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue* queue, int size) {
    queue->nodes = (QueueNode*)malloc(size * sizeof(QueueNode));
    queue->front = 0;
    queue->rear = -1;
    queue->size = size;
}

// 入队操作
void enqueue(Queue* queue, QueueNode node) {
    if (queue->rear == queue->size - 1) {
        printf("Queue is full.\n");
        return;
    }
    queue->rear++;
    queue->nodes[queue->rear] = node;
}

// 出队操作
QueueNode dequeue(Queue* queue) {
    if (queue->front > queue->rear) {
        printf("Queue is empty.\n");
        QueueNode emptyNode = {{-1, -1}, -1};
        return emptyNode;
    }
    QueueNode node = queue->nodes[queue->front];
    queue->front++;
    return node;
}

// 判断坐标是否合法
int isValidCoordinate(int x, int y) {
    return (x >= 0 && x < ROWS && y >= 0 && y < COLS);
}

// 判断坐标是否为终点
int isDestination(Coordinate coord, Coordinate destination) {
    return (coord.x == destination.x && coord.y == destination.y);
}

// 进行广度优先搜索
int bfs(int map[ROWS][COLS], Coordinate start, Coordinate destination) {
    int visited[ROWS][COLS] = {0}; // 记录是否访问过
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

    Queue queue;
    initQueue(&queue, ROWS * COLS);

    QueueNode startNode = {start, 0};
    enqueue(&queue, startNode);
    visited[start.x][start.y] = 1;

    while (queue.front <= queue.rear) {
        QueueNode currentNode = dequeue(&queue);
        Coordinate currentCoord = currentNode.coord;
        int currentDistance = currentNode.distance;

        if (isDestination(currentCoord, destination)) {
            return currentDistance;
        }

        for (int i = 0; i < 4; i++) {
            int newX = currentCoord.x + directions[i][0];
            int newY = currentCoord.y + directions[i][1];

            if (isValidCoordinate(newX, newY) && map[newX][newY] == 0 && !visited[newX][newY]) {
                Coordinate newCoord = {newX, newY};
                QueueNode newNode = {newCoord, currentDistance + 1};
                enqueue(&queue, newNode);
                visited[newX][newY] = 1;
            }
        }
    }

    return -1; // 没有找到可行路径
}

int main() {
    int map[ROWS][COLS] = {
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 1, 1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 0, 1, 0},
        {0, 1, 1, 1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0}
    };

    Coordinate start, destination;

    printf("Please input the start position (x y): ");
    scanf("%d %d", &start.x, &start.y);

    printf("Please input the destination position (x y): ");
    scanf("%d %d", &destination.x, &destination.y);

    int distance = bfs(map, start, destination);

    if (distance != -1) {
        printf("The robot can reach the destination in %d steps.\n", distance);
    } else {
        printf("The robot cannot reach the destination.\n");
    }

    return 0;
}

在上面的代码中，我们使用了广度优先搜索（BFS）算法来进行机器人的路径规划。首先，我们定义了坐标结构体Coordinate，用于表示二维数组中的位置。然后，我们定义了队列节点结构体QueueNode和队列结构体Queue，用于实现BFS算法中的队列操作。

在bfs函数中，我们使用一个二维数组visited来记录每个位置是否已经访问过，避免重复访问。我们使用一个队列来存储待访问的节点，初始时将起点入队，并将起点标记为已访问。然后，在队列不为空的情况下，不断从队列中取出节点进行扩展。对于每个节点，我们分别判断上、下、左、右四个方向的相邻位置是否合法（即在地图范围内），是否为可通行的位置（即值为0），以及是否已经访问过。如果满足条件，则将该相邻位置入队，并标记为已访问。如果找到终点位置，则返回当前距离。

在主函数中，我们先定义了一个8×8的地图map，其中1表示障碍物，0表示可通行的位置。然后，通过用户输入获取机器人的起点位置和终点位置。调用bfs函数进行路径规划，并输出机器人到达终点需要的步数。