C语言分支限界法求迷宫问题案例代码

题目描述

分支限界法求迷宫问题，走迷宫得出最短路径，迷宫自己设置一个n×m的矩阵，输入n,m和迷宫初态，输出最短路径，若无解就输出no way

案例代码

下面是一个用 C 语言实现的简单案例，使用分支限界法求解迷宫问题，找到最短路径。在这个示例中，我们假设迷宫中 0 表示可以通过的路径，1 表示墙壁。

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

#define MAX_ROW 10
#define MAX_COL 10

typedef struct {
    int row;
    int col;
} Point;

typedef struct {
    Point point;
    int distance;
} QueueNode;

typedef struct {
    QueueNode items[MAX_ROW * MAX_COL];
    int front, rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = -1;
    return queue;
}

bool isEmpty(Queue* queue) {
    return queue->front == -1;
}

void enqueue(Queue* queue, QueueNode node) {
    if (queue->rear == MAX_ROW * MAX_COL - 1) {
        printf("Queue is full.\n");
        exit(EXIT_FAILURE);
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear++;
    queue->items[queue->rear] = node;
}

QueueNode dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        exit(EXIT_FAILURE);
    }
    QueueNode node = queue->items[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    return node;
}

bool isValid(int row, int col, int n, int m) {
    return (row >= 0) && (row < n) && (col >= 0) && (col < m);
}

int shortestPath(int maze[MAX_ROW][MAX_COL], int n, int m, Point start, Point end) {
    int dRow[] = {-1, 0, 0, 1};
    int dCol[] = {0, -1, 1, 0};

    Queue* queue = createQueue();
    bool visited[MAX_ROW][MAX_COL] = {false};

    QueueNode startNode = {start, 0};
    enqueue(queue, startNode);
    visited[start.row][start.col] = true;

    while (!isEmpty(queue)) {
        QueueNode currentNode = dequeue(queue);
        Point currentPoint = currentNode.point;
        int currentDistance = currentNode.distance;

        if (currentPoint.row == end.row && currentPoint.col == end.col) {
            return currentDistance;
        }

        for (int i = 0; i < 4; i++) {
            int newRow = currentPoint.row + dRow[i];
            int newCol = currentPoint.col + dCol[i];
            if (isValid(newRow, newCol, n, m) && maze[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                QueueNode newNode = {{newRow, newCol}, currentDistance + 1};
                enqueue(queue, newNode);
                visited[newRow][newCol] = true;
            }
        }
    }

    return -1; // No path found
}

int main() {
    int n, m;
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &n, &m);

    printf("Enter the maze:\n");
    int maze[MAX_ROW][MAX_COL];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    Point start, end;
    printf("Enter the starting position (row col): ");
    scanf("%d %d", &start.row, &start.col);
    printf("Enter the ending position (row col): ");
    scanf("%d %d", &end.row, &end.col);

    int distance = shortestPath(maze, n, m, start, end);
    if (distance == -1) {
        printf("No way.\n");
    } else {
        printf("Shortest path distance: %d\n", distance);
    }

    return 0;
}

这个程序首先让用户输入迷宫的行数和列数，然后输入迷宫的初始状态，以及起点和终点的位置。程序使用了队列来进行广度优先搜索，找到起点到终点的最短路径。如果不存在路径，则输出 “No way.”。