如何获取网格中两个节点之间的路径？

Question

我想做一个函数，它可以给出一个简单矩阵中两个元素之间可能路径的坐标。到目前为止，我已经设法确定两者之间是否有路径，但是，我正在拔头发以确定路径的坐标。我在考虑一个链表，其中指针指向下一个可到达的相邻元素。但是，我觉得应该有一种更简单的方法来做到这一点。

---

更新一：

我开始根据 sp2danny 评论创建解决方案，但不幸的是，它给了我非常奇怪的连接错误

unvisitedNeighbours

：

unvisitedNeighbours[0].pMain=错误：类型 'std::queue >' 没有 提供下标运算符

还有一个错误：

this->parent->parent->parent.parent.parent= 错误：在非静态成员函数之外无效使用'this'

错误发生在将 src 元素推入队列之后。

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

using namespace std;

#define row 5
#define col 5

struct node {
    pair<int, int> pMain;
    pair<int, int> parent;
    int index;

    node(pair<int, int> _p, pair<int, int> _parent, int _index) {
        pMain = _p;
        parent = _parent;
        int index = _index;
    }
};

// to find the path from
// top left to bottom right
bool isPath(int arr[row][col]) {
    // directions
    int dir[4][2] = {{0,  1},{0,  -1},{1,  0},{-1, 0}};

    // queue
    queue<node> unvisitedNeighbours;

    // insert the top right corner.

    node Node(node(make_pair(0, 0), make_pair(-1, -1), 0));
    unvisitedNeighbours.emplace(Node);

    std::vector<node> pathes;
    pathes.push_back(Node);

    // until queue is empty
    while (!unvisitedNeighbours.empty()) {
        node p = unvisitedNeighbours.front();
        unvisitedNeighbours.pop();

        // mark as visited
        arr[p.pMain.first][p.pMain.second] = -1;

        // destination is reached.
        if (p.pMain == make_pair(row - 1, col - 1)) {
            int index = p.index;
            while (index != 0) {
                std::cout << pathes.at(index).pMain.first << " " << pathes.at(index).pMain.second << endl;
                index = pathes.at(index).index;
            }
            return true;
        }

        // check all four directions
        for (int i = 0; i < 4; i++) {
            // using the direction array
            int a = p.pMain.first + dir[i][0];
            int b = p.pMain.second + dir[i][1];

            // not blocked and valid
            if (arr[a][b] != -1 && a >= 0 && b >= 0
                && a < row && b < col) {
                pathes.push_back(node(make_pair(a, b), p.pMain, pathes.size() - 1));
                unvisitedNeighbours.push(node(make_pair(a, b), p.pMain, pathes.size() - 1));

            }
        }
    }
    return false;
}

// Driver Code
int main() {
    // Given array
    int arr[row][col] = {{0,  0, 0,  -1, 0},
                         {-1, 0, 0,  -1, -1},
                         {0,  0, 0,  -1, 0},
                         {-1, 0, 0,  0,  0},
                         {0,  0, -1, 0,  0}};

    // path from arr[0][0] to arr[row][col]
    if (isPath(arr))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

Answer 1

基本上，您正在尝试找到未加权图的最短路径。 这里的图是一个二维网格。

要打印路径，您只需要在访问节点时跟踪节点及其父节点即可。

这里是示例代码：

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

int dirX[] = {-1, 0, 0, 1};
int dirY[] = {0, -1, 1, 0};

bool IsValid(int& r, int& c, int &totalRow, int& totalCol)
{
    return (r >= 0 && r < totalRow && c >= 0 && c < totalCol);
}

int BFS(vector<vector<int>>& grid, pair<int, int> source, pair<int, int> destination, map<pair<int, int>, pair<int, int>>& parent)
{
    int totalRow = grid.size();
    int totalCol = grid[0].size();
    vector<vector<int>> visited(totalRow, vector<int> (totalCol, 0));
    vector<vector<int>> level(totalRow, vector<int> (totalCol, 0));
    queue<pair<int, int>> q;
    q.push(source);
    parent[source] = { -1, -1 };

    while (!q.empty())
    {
        pair<int, int> curr = q.front();
        q.pop();
        visited[curr.first][curr.second] = true;

        for (int d = 0; d < 4; d++)
        {
            int nextR = curr.first + dirX[d];
            int nextC = curr.second + dirY[d];
            if (IsValid(nextR, nextC, totalRow, totalCol) && grid[nextR][nextC] != -1 && !visited[nextR][nextC])
            {
                level[nextR][nextC] = 1 + level[curr.first][curr.second];
                visited[nextR][nextC] = true;
                parent[{nextR, nextC}] = curr;
                q.push({nextR, nextC});

                if (make_pair(nextR, nextC) == destination)
                {
                    return level[nextR][nextC];
                }
            }
        }
    }

    return -1;
}

void PrintShortestPath(vector<vector<int>> &grid, pair<int, int> source, pair<int, int> destination)
{
    map<pair<int, int>, pair<int, int>> parent;
    int shortestDistance = BFS(grid, source, destination, parent);
    if (shortestDistance == -1)
    {
        cout << "No path available!" << endl;
    }
    else
    {
        vector<pair<int, int>> path;
        pair<int, int> currentNode = destination;
        path.push_back(destination);
        cout << "Shortest distance: " << shortestDistance << endl;

        while (parent[currentNode] != make_pair(- 1, -1))
        {
            path.push_back(parent[currentNode]);
            currentNode = parent[currentNode];
        }

        for (auto &curr : path)
        {
            cout << curr.first << " " << curr.second << endl;
        }
    }
}

int main()
{
    vector<vector<int>> grid
    {
        {0,  0, 0,  -1, 0},
        {-1, 0, 0,  -1, -1},
        {0,  0, 0,  -1, 0},
        {-1, 0, 0,  0,  0},
        {0,  0, -1, 0,  0}
    };

    PrintShortestPath(grid, { 0, 0 }, { 4, 4 });
}

注意：如果你在谷歌搜索“Print shortest path of an unweighted graph”，你将能够找到更多相关信息。

关于错误，你正在进入你的代码

在构造函数中，您已经编写了

int index = _index

。因此，没有分配正确的索引值。

所以在访问

pathes.at(index)

的时候，就出现了错误

node(pair<int, int> _p, pair<int, int> _parent, int _index)
{
    pMain = _p;
    parent = _parent;
    index = _index;
}