C++网格最短路径算法改造咨询：如何打印路径所有节点坐标

核心实现逻辑为在原有BFS遍历流程中新增前驱节点记录矩阵，每访问一个合法节点时同步记录它的上一跳坐标，匹配到终点后反向回溯即可得到完整的正序路径。

修改后的完整代码 #

#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
using namespace std;

// 8方向移动偏移量
int dirs[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

bool isValid(vector<vector<int>>& grid, int i, int j) {
    if(i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] != 0)
        return false;
    return true;
}

// 返回值第一个元素为路径长度，无路径返回-1；第二个元素为路径坐标列表
pair<int, vector<pair<int, int>>> shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if(grid.empty())
        return {0, {}};

    int m = grid.size(), n = grid[0].size();
    pair<int, int> start = {0,0};
    pair<int, int> end = {m-1, n-1};
    if(grid[start.first][start.second] == 1 || grid[end.first][end.second] == 1) 
        return {-1, {}};

    vector<vector<bool>> visited(m, vector<bool>(n, false));
    // 前驱节点矩阵，初始值{-1,-1}代表无上游节点
    vector<vector<pair<int, int>>> parent(m, vector<pair<int, int>>(n, {-1, -1}));
    vector<pair<int,int>> q;
    q.push_back(start);
    visited[start.first][start.second] = true;
    int count = 1;

    while(!q.empty()) {
        vector<pair<int,int>> q2;
        for(auto const& cur: q) {
            if(cur.first == end.first && cur.second == end.second) {
                // 回溯得到路径
                vector<pair<int, int>> path;
                pair<int, int> curr = end;
                while(curr.first != -1 && curr.second != -1) {
                    path.push_back(curr);
                    curr = parent[curr.first][curr.second];
                }
                reverse(path.begin(), path.end());
                return {count, path};
            }
            for(auto &dir : dirs) {
                int x = cur.first + dir[0];
                int y = cur.second + dir[1];
                if(isValid(grid, x, y) && !visited[x][y]) {
                    visited[x][y] = true;
                    parent[x][y] = cur;
                    q2.push_back({x, y});
                }
            }
        }
        count++;
        q = q2;
    }
    return {-1, {}};
}

// 路径格式化输出示例
void printPath(vector<pair<int, int>>& path) {
    for(int i = 0; i < path.size(); i++) {
        if(i > 0) cout << "->";
        cout << "[" << path[i].first << "][" << path[i].second << "]";
    }
    cout << endl;
}

代码说明 #

• 新增parent二维数组：专门存储每个坐标对应的前驱节点，初始值{-1, -1}用于标识起点的上游为空，作为回溯的终止条件
• 修正了原代码的方向偏移判断逻辑：仅当邻居坐标合法时才进行访问校验，避免无效逻辑判断
• 路径回溯逻辑：匹配到终点后，从终点坐标开始反向遍历parent数组直到起点，反转后得到从起点到终点的正序路径
• 输出的路径可直接通过printPath函数格式化为你需要的[x][y]->[x][y]样式

内容的提问来源于stack exchange，提问作者Zeyan Wang