步骤:

  1. 引入必要的头文件和命名空间。
  2. 定义全局常量INF,表示无穷大。
  3. 定义一个辅助函数isValid,用于判断一个坐标是否在网格范围内。
  4. 定义最短路径函数shortestPath,接受参数n和m表示网格的行数和列数,sxsy表示起点的坐标,txty表示终点的坐标,grid是一个存储网格信息的二维字符数组。
  5. 创建一个二维数组dist,用于保存起点到每个位置的最短路径长度,初始值均为INF
  6. 创建一个队列q,并将起点坐标入队,将起点到起点的距离dist[sx][sy]设为0。
  7. 当队列不为空时,循环执行以下操作: a. 取出队列中的一个坐标(x, y)。 b. 如果当前坐标为终点坐标(tx, ty),则返回dist[tx][ty],即起点到终点的最短路径长度。 c. 遍历四个方向(上(0,1)、下(0,-1)、左(-1,0)、右(1,0)),计算下坐标(nx, ny)。 d. 如果下一个坐标有效(在网格范围内)并且是可通行的('.'),且下一个坐标到起点的距离为INF(即未被访问过),则将下一个坐标入队,更新dist[nx][ny]为dist[x][y]+1。
  8. 如果循环结束后仍未找到终点坐标,则返回-1,表示无法从起点达终点。
  9. 在主函数main中,首先读入网格的行数n和列数m,然后读入起点和终点的坐标。
  10. 创建一个二维字符数组grid,用于存储网格信息,利用个嵌套循环读入网格字符。
  11. 调用shortestPath函数,将起点和终点坐标减一后传入,得到最短路径长度,并将结果输出。(起点和终点的坐标在输入时被减去了1,是因为在代码中使用的数组下标从0开始,而输入时的坐标是从1开始的。
  12. 返回0,表示程序正常结束。

代码如下:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

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

int shortestPath(int n, int m, int sx, int sy, int tx, int ty, vector<vector<char>>& grid) {
    vector<vector<int>> dist(n, vector<int>(m, INF));
    queue<pair<int, int>> q;
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};

    q.push(make_pair(sx, sy));
    dist[sx][sy] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == tx && y == ty) {
            return dist[x][y];
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(nx, ny, n, m) && grid[nx][ny] == '.' && dist[nx][ny] == INF) {
                q.push(make_pair(nx, ny));
                dist[nx][ny] = dist[x][y] +1;
            }
        }
    }

    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;

    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    int result = shortestPath(n, m, sx - 1, sy - 1, tx - 1, ty - 1, grid);
    cout << result << endl;

    return 0;
}