我想做一个函数,它可以给予一个简单矩阵中两个元素之间可能路径的坐标。到现在为止,我已经设法确定,是否有可能存在两个之间的路径,然而,我拔出我的头发来确定路径的坐标。我在考虑一个链表,其中指针指向下一个可到达的相邻元素。然而,我觉得,应该有一个更简单的方法来实现。
更新1:
我开始根据sp2 danny的评论创建解决方案,但不幸的是,它在与unvisitedNeighbours
的连接中给了我非常奇怪的错误:
未访问的邻居[0]。pMain=错误:类型“std::queue〈node,std::deque〈node,std::allocator〉〉”未提供下标运算符
还有一个错误:
this-〉parent-〉parent-〉parent.parent.parent= error:在非静态成员函数之外使用“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;
}
1条答案
按热度按时间3qpi33ja1#
基本上,你试图找到一个未加权图的最短路径。这里的图是一个2D网格。
要打印路径,您只需要在访问节点及其父节点时跟踪它们。
下面是一个示例代码:
注意:如果你在谷歌搜索“打印未加权图的最短路径”,你将能够找到更多关于它的信息。
关于错误,你正在进入你的代码
在构造函数中,您已经编写了
int index = _index
。因此,没有分配正确的索引值。因此,在访问
pathes.at(index)
时,发生了错误。