我正在做一个项目，我需要找到从单一来源到单一目的地的最短路径。我只能右转，所以有时我需要右转三个而不是左转。我已经把算法弄下来了(我想)，但是我在打印之后采用的路径时遇到了问题。我在每个图 block 上保留一个来自指针，但是当我从最后开始并遵循来自指针时，获得三个权利的时间导致循环，因为来自指针被更新的指针覆盖.我如何识别此循环模式并回到正轨以打印完整路径？
这是我的 backTracker 类
class backTracker {
int rows;
int cols;
tile** map;
tile* start;
tile* end;
int rightTurns;
int loopTracker;
bool done;
int** visits;
MyStack visited;
public:
backTracker(int inRows, int inCols, tile** inMap, tile* inStart,
tile* inEnd, int** &inVisits) {
rows = inRows;
cols = inCols;
map = inMap;
start = inStart;
end = inEnd;
rightTurns = 0;
loopTracker = 0;
done = false;
visits = inVisits;
}
void findPath() {
backTrack(start);
}
private:
void backTrack(tile* currTile) {
if (currTile == end || done) {
cout << "end found" << endl;
done = true;
return;
}
else if (promising(currTile)) {
//if it's the start tile, check all directions
if (currTile->cameFrom == 0) {
tile* next;
int cRow = currTile->row;
int cCol = currTile->col;
if (cRow != 0) {
next = &map[cRow-1][cCol];
next->cameFrom = currTile;
next->directionFrom = 'N';
backTrack(next);
}
if (cRow != rows - 1) {
next = &map[cRow+1][cCol];
next->cameFrom = currTile;
next->directionFrom = 'S';
backTrack(next);
}
if (cCol != cols - 1) {
next = &map[cRow][cCol+1];
next->cameFrom = currTile;
next->directionFrom = 'E';
backTrack(next);
}
if (cCol != 0) {
next = &map[cRow][cCol-1];
next->cameFrom = currTile;
next->directionFrom = 'W';
backTrack(next);
}
}
//otherwise check straight and right
else {
currTile->straight = 0; //the tile in the straight direction
currTile->right = 0;//the tile to the right of the straight tile
//easier to read
int row = currTile->row;
int col = currTile->col;
bool good = false;
//find the straight and right tiles depending on current
//direction, also check if the tile has been visited from
//that direction already
if (currTile->directionFrom == 'N') {
if (col != cols - 1) {
if (map[row][col+1].directionFrom != 'E') {
currTile->right = &map[row][col+1];
currTile->right->directionFrom = 'E';
good = true;
tile* right = currTile->right;
right->cameFrom = currTile;
backTrack(right);
}
}
if (row != 0) {
//if it hasn't already been visited from this direction
if (map[row-1][col].directionFrom != 'N') {
currTile->straight = &map[row-1][col];
good = true;
tile* str = currTile->straight;
str->cameFrom = currTile;
//going straight so direction is the same
str->directionFrom = currTile->directionFrom;
backTrack(str);
}
}
}
else if (currTile->directionFrom == 'W') {
if (row != 0) {
if (map[row-1][col].directionFrom != 'N') {
currTile->right = &map[row-1][col];
currTile->right->directionFrom = 'N';
good = true;
tile* right = currTile->right;
right->cameFrom = currTile;
backTrack(right);
}
}
if (col != 0) {
if (map[row][col-1].directionFrom != 'W') {
currTile->straight = &map[row][col-1];
good = true;
tile* str = currTile->straight;
str->cameFrom = currTile;
//going straight so direction is the same
str->directionFrom = currTile->directionFrom;
backTrack(str);
}
}
}
else if (currTile->directionFrom == 'S') {
if (col != 0) {
if (map[row][col-1].directionFrom != 'W') {
currTile->right = &map[row][col-1];
currTile->right->directionFrom = 'W';
good = true;
tile* right = currTile->right;
right->cameFrom = currTile;
backTrack(right);
}
}
if (row != rows - 1) {
if (map[row+1][col].directionFrom != 'S') {
currTile->straight = &map[row+1][col];
good = true;
tile* str = currTile->straight;
str->cameFrom = currTile;
//going straight so direction is the same
str->directionFrom = currTile->directionFrom;
backTrack(str);
}
}
}
else if (currTile->directionFrom == 'E'){
if (row != row - 1) {
if (map[row+1][col].directionFrom != 'S') {
currTile->right = &map[row+1][col];
currTile->right->directionFrom = 'S';
good = true;
tile* right = currTile->right;
right->cameFrom = currTile;
backTrack(right);
}
}
if (col != cols - 1) {
if (map[row][col+1].directionFrom != 'E') {
currTile->straight = &map[row][col+1];
good = true;
tile* str = currTile->straight;
str->cameFrom = currTile;
//going straight so direction is the same
str->directionFrom = currTile->directionFrom;
backTrack(str);
}
}
}
}
}
}
//checks for walls
bool promising(tile* currTile) {
if (currTile->type == WALL) {
return false;
}
else {
return true;
}
}
最佳答案
在每个单元格中存储几条(最多四条)信息。我不知道你是如何搜索你的矩阵的，但我会用某种广度优先算法来做到这一点，该算法会尝试找到从所有四个方向到每个单元格的路径。每个单元格必须存储从所有四个方向到达该单元格必须采取的步数。一旦到达目的地，此路径构建就会停止。要重新创建路径，然后倒退并迭代地找到距离当前单元格的目的地少一步的相邻单元格。
关于c++ - 最短路径、禁止左转、打印路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8460207/