最短路径、禁止左转、打印路径

Question

我正在做一个项目，我需要找到从单个源到单个目的地的最短路径。我只能右转，所以有时我需要右转三个而不是左转。我已经确定了算法（我认为），但在打印随后采取的路径时遇到问题。我在每个图块上保留一个来自指针，但是当我从末尾开始并遵循来自指针时，获取三个权限的时间会导致循环，因为来自指针被较新的指针覆盖。我怎样才能识别这个循环模式并回到正轨来打印完整路径？

这是我的 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;
            }
    }

Answer 1

每个单元格中存储几条（最多四条）信息。我不知道你如何搜索矩阵，但我会使用某种广度优先算法来执行此操作，该算法会尝试找到从所有四个方向到每个单元格的路径。每个单元格必须存储从所有四个方向到达该单元格所必须采取的步数。一旦到达目的地，该路径构建就会停止。要重新创建路径，请向后并迭代地查找距当前单元格的目的地少一步的相邻单元格。