求矩阵左上角到右下角的最短路径C语言

在C语言中，求解矩阵从左上角到右下角的最短路径通常可以使用动态规划（Dynamic Programming）中的“宽度优先搜索”（Breadth First Search，简称BFS）算法，特别是适用于二维数组的情况，比如Floyd-Warshall算法。不过在这里我会讲解最简单的版本——广度优先搜索。

首先，假设给定的是一个非负整数网格，我们可以创建一个队列来存储待访问的节点，并维护一个二维数组来记录每个节点的最短距离。算法步骤如下：

1. 初始化两个变量，`dx[]`和`dy[]`，分别表示水平和垂直移动的步长，对于正方形矩阵它们都是1。
2. 将起点(0, 0)的距离设为0，其余位置设为无穷大（通常用很大的数值如INT_MAX）。
3. 创建一个队列，将起点加入并设置其距离为0。
4. 当队列不为空时，执行循环：
a. 弹出队首元素（当前位置），标记为已访问。
b. 对于当前位置的四个相邻节点（上、下、左、右），如果新路径长度比当前记录的更小，则更新该节点的距离，并将其加入队列。
5. 循环结束后，终点的值就是从左上角到右下角的最短路径。

C语言代码示例：

#include <stdio.h>
#define ROWS 4
#define COLS 4

int minDistance(int dist[ROWS][COLS], int x, int y) {
    return (x >= 0 && x < ROWS && y >= 0 && y < COLS) ? dist[x][y] : INT_MAX;
}

void shortestPath(int maze[ROWS][COLS], int dist[ROWS][COLS]) {
    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};

    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (i == 0 && j == 0) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INT_MAX;
            }
        }
    }

    int queue[ROWS * COLS], front = 0, rear = 0;
    queue[rear++] = 0; // Start from top-left cell
    dist[0][0] = 0;

    while (front != rear) {
        int x = queue[front++];
        int y = x % ROWS;
        int currDist = dist[x / ROWS][y];

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

            if (maze[newX][newY] == 0 && minDistance(dist, newX, newY) > currDist + 1) {
                dist[newX][newY] = currDist + 1;
                queue[rear++] = newX;
            }
        }
    }

    printf("Shortest distance: %d\n", dist[ROWS - 1][COLS - 1]);
}

// Example usage:
int main() {
    int maze[ROWS][COLS] = { {0, 1, 0, 0},
                            {1, 1, 0, 1},
                            {0, 0, 0, 0},
                            {1, 0, 0, 0} };
    int dist[ROWS][COLS];

    shortestPath(maze, dist);
    return 0;
}