7-44 迷宫变种-最短路径

下面图示表示一个迷宫，四周为-1表示围墙,内部为-1表示障碍,权 值1、2、5、9表示经过需要消耗的能量代价。请找出从入口(3,6)到出口(8,8),老鼠消耗能量最小的路径(注意本题是四个方向的迷宫)

输入格式:

第一行：迷宫的大小m n ，分别表示迷宫的长和高
第二行：入口和出口
其余行：迷宫的矩阵表示
提示：用65535为无穷大

输出格式:

输出为老鼠消耗能量最小的路径，以逆序输出

输入样例:

在这里给出一组输入。例如：

10 10
3 6 8 8
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  2  1  1  1  1  1  5  1 -1
-1  1  9  9  9  1  1 -1  1 -1
-1  1  1  1  1  1  1 -1  1 -1
-1  1 -1 -1 -1 -1 -1 -1  1 -1
-1  1  9  9  9  1  1  1  1 -1
-1  1  1  1  1  1  1  1  1 -1
-1  1  1  1  1  1  1  1  1 -1
-1  1  1  1  1  1  1  1  2 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出样例:

在这里给出相应的输出。例如：

(8 8)(7 8)(6 8)(5 8)(4 8)(3 8)(2 8)(1 8)(1 7)(1 6)(2 6)(3 6)

?

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

#define MAX_MAZE_SIZE 10
#define INF 65535

typedef struct {
    int x, y;
    int cost;
} Node;

typedef struct {
    Node data[MAX_MAZE_SIZE * MAX_MAZE_SIZE];
    int size;
} PriorityQueue;

int maze[MAX_MAZE_SIZE][MAX_MAZE_SIZE];
int m, n;
int entryX, entryY, exitX, exitY;
int energy[MAX_MAZE_SIZE][MAX_MAZE_SIZE];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

PriorityQueue* createPriorityQueue() {
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->size = 0;
    return pq;
}

void enqueue(PriorityQueue* pq, Node node) {
    pq->data[pq->size++] = node;

    int i = pq->size - 1;
    while (i > 0 && pq->data[i].cost < pq->data[(i - 1) / 2].cost) {
        Node temp = pq->data[i];
        pq->data[i] = pq->data[(i - 1) / 2];
        pq->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

Node dequeue(PriorityQueue* pq) {
    Node minNode = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;

    int i = 0;
    while (2 * i + 1 < pq->size) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int minChild = leftChild;

        if (rightChild < pq->size && pq->data[rightChild].cost < pq->data[leftChild].cost)
            minChild = rightChild;

        if (pq->data[i].cost <= pq->data[minChild].cost)
            break;

        Node temp = pq->data[i];
        pq->data[i] = pq->data[minChild];
        pq->data[minChild] = temp;

        i = minChild;
    }

    return minNode;
}

bool isValid(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != -1;
}

int min(int a, int b) {
    return a < b ? a : b;
}

void aStar() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            energy[i][j] = INF;
        }
    }

    PriorityQueue* pq = createPriorityQueue();
    Node start = { entryX, entryY, 0 };
    enqueue(pq, start);
    energy[entryX][entryY] = 0;

    while (pq->size > 0) {
        Node current = dequeue(pq);

        if (current.x == exitX && current.y == exitY) {
            return;
        }

        for (int i = 0; i < 4; i++) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];

            if (isValid(newX, newY)) {
                int newCost = current.cost + maze[newX][newY];
                int minCost = min(energy[newX][newY], newCost);

                if (minCost < energy[newX][newY]) {
                    energy[newX][newY] = minCost;
                    Node neighbor = { newX, newY, minCost };
                    enqueue(pq, neighbor);
                }
            }
        }
    }
}

int main() {
    // Read input
    scanf("%d %d", &m, &n);
    scanf("%d %d %d %d", &entryX, &entryY, &exitX, &exitY);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    // Run A* algorithm
    aStar();

    // Print path
    printf("(%d %d)", exitX, exitY);
    int x = exitX;
    int y = exitY;

    while (x != entryX || y != entryY) {
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (isValid(newX, newY) && energy[x][y] - maze[x][y] == energy[newX][newY]) {
                printf("(%d %d)", newX, newY);
                x = newX;
                y = newY;
                break;
            }
        }
    }

    return 0;
}

?