步骤:
- 引入必要的头文件和命名空间。
- 定义全局常量INF,表示无穷大。
- 定义一个辅助函数isValid,用于判断一个坐标是否在网格范围内。
- 定义最短路径函数shortestPath,接受参数n和m表示网格的行数和列数,sx和sy表示起点的坐标,tx和ty表示终点的坐标,grid是一个存储网格信息的二维字符数组。
- 创建一个二维数组dist,用于保存起点到每个位置的最短路径长度,初始值均为INF。
- 创建一个队列q,并将起点坐标入队,将起点到起点的距离dist[sx][sy]设为0。
- 当队列不为空时,循环执行以下操作: 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。
- 如果循环结束后仍未找到终点坐标,则返回-1,表示无法从起点达终点。
- 在主函数main中,首先读入网格的行数n和列数m,然后读入起点和终点的坐标。
- 创建一个二维字符数组grid,用于存储网格信息,利用个嵌套循环读入网格字符。
- 调用shortestPath函数,将起点和终点坐标减一后传入,得到最短路径长度,并将结果输出。(起点和终点的坐标在输入时被减去了1,是因为在代码中使用的数组下标从0开始,而输入时的坐标是从1开始的。)
- 返回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; }