C++程序矩阵或网格中两个单元格之间的最短距离

1. 简介

在很多应用场景中，需要计算矩阵或网格中两个单元格之间的最短距离，例如在电子游戏中，角色需要找到最短路径来到达目的地。本文将介绍如何用C++来实现这一功能。

2. 解决方案

我们可以使用BFS（Breadth-First Search）算法来解决这个问题。具体来讲，我们可以看作是在一个有向图中寻找从起点到终点的最短路径。当图中每个边的权值都相同时，BFS算法能够保证找到的路径是最短路径。

下面是一个简单的BFS算法实现，用于计算从起点到终点的最短路径：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100;
int grid[MAXN][MAXN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int shortestPath(int sx, int sy, int ex, int ey, int n, int m) {
    queue<pair<int, int>> q;
    int dist[n][m];
    memset(dist, -1, sizeof(dist));
    q.push(make_pair(sx, sy));
    dist[sx][sy] = 0;
    while (!q.empty()) {
        pair<int, int> u = q.front();
        q.pop();
        int x = u.first, y = u.second;
        if (x == ex && y == ey) return dist[ex][ey];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1 && grid[nx][ny] == 0) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return -1;
}

以上代码中，我们通过BFS算法，计算了从(sx, sy)到(ex, ey)的最短距离。需要注意的是，我们把起点标记为0，对于其他的单元格，一开始我们将它们的距离都标记为-1。同时，我们需要保证在遍历网格时，不遍历到障碍物（这里用0表示），否则会使距离增加。最后，如果找到了终点，则返回距离，否则返回-1表示到不了终点。

3. 示例

下面是一个简单的例子，来演示如何使用以上的代码计算最短路径：

#include <iostream>
using namespace std;

const int MAXN = 100;
int grid[MAXN][MAXN];

int main() {
    int n, m, sx, sy, ex, ey;
    cin >> n >> m >> sx >> sy >> ex >> ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    cout << shortestPath(sx, sy, ex, ey, n, m) << endl;
    return 0;
}

在上述程序中，我们先输入网格的大小以及起点和终点的坐标。接着，我们输入网格中每个单元格的状态（0表示通路，1表示障碍物）。最后，我们调用shortestPath函数来计算最短路径。