Как использовать рекурсию, чтобы найти и распечатать несколько кратчайших путей из точки А в точку Б?(C ++) - PullRequest
Новая
       8

Как использовать рекурсию, чтобы найти и распечатать несколько кратчайших путей из точки А в точку Б?(C ++)

0 голосов
/ 03 февраля 2019

Первый пост здесь, так что прости меня, если я что-то делаю неправильно.Я не могу понять, как рекурсивно найти и распечатать все кратчайшие пути из точки A в точку B.

Я делаю программу, в которой робот переходит из точки A в точку B, используя кратчайший возможный путь.Программа должна использовать рекурсию, находить и распечатывать все кратчайшие пути, которые робот может пройти из точки А, чтобы добраться до точки Б. Например, если робот стартует в точке (1, 2) и ему необходимо пройти путь до точки(3, 5), тогда программа должна напечатать 10 путей всего за 5 ходов (например, NNNEE).Вот две наиболее важные функции, извините, что код такой грязный. 

void Robot::FindPath(const Board &board)
{
    string path = "";
    vector < string > pathsVector;
    MoveRobot(startingX,
              startingY,
              treasureX,
              treasureY,
              path,
              "",
              0,
              pathsVector);
}

void Robot::MoveRobot(const int &startingX,
                      const int &startingY,
                      const int &treasureX,
                      const int &treasureY,
                      const string &path,
                      const string &lastMove,
                      const int &numMovesDirection,
                      vector<string> &pathVector)
{
    if (startingX == treasureX && startingY == treasureY)
    {
        cout << path << endl;
        PathCount++;
        pathVector.push_back(path);
        return;
    }
    else if (startingY == treasureY)
    {
        if (startingX - treasureX > 0)
        {
            if (lastMove == "W" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "W" && 
                      (numMovesDirection < MaxStepsDir || 
                       numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX - 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "W",
                          "W",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "W")
            {
                MoveRobot(startingX - 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "W",
                          "W",
                          1,
                          pathVector);
            }
        }
        else if (startingX - treasureX < 0)
        {
            if (lastMove == "E" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "E" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX + 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "E",
                          "E",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "E")
            {
                MoveRobot(startingX + 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "E",
                          "E",
                          1,
                          pathVector);
            }
        }
    }
    else if (startingX == treasureX)
    {
        if (startingY - treasureY > 0)
        {
            if (lastMove == "S" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "S" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX,
                          startingY - 1,
                          treasureX,
                          treasureY,
                          path + "S",
                          "S",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "S")
            {
                MoveRobot(startingX,
                          startingY - 1,
                          treasureX,
                          treasureY,
                          path + "S",
                          "S",
                          1,
                          pathVector);
            }
        }
        else if (startingY + treasureY > 0)
        {
            if (lastMove == "N" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "N" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX,
                          startingY + 1,
                          treasureX,
                          treasureY,
                          path + "N",
                          "N",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "N")
            {
                MoveRobot(startingX,
                          startingY + 1,
                          treasureX,
                          treasureY,
                          path + "N",
                          "N",
                          1,
                          pathVector);
            }
        }
    }
    else
    {
        if (startingX - treasureX > 0)
        {
            if (lastMove == "W" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "W" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX - 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "W",
                          "W",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "W")
            {
                MoveRobot(startingX - 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "W",
                          "W",
                          1,
                          pathVector);
            }
        }
        else if (startingX - treasureX < 0)
        {
            if (lastMove == "E" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "E" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX + 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "E",
                          "E",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "E")
            {
                MoveRobot(startingX + 1,
                          startingY,
                          treasureX,
                          treasureY,
                          path + "E",
                          "E",
                          1,
                          pathVector);
            }
        }
        else if (startingY - treasureY > 0)
        {
            if (lastMove == "S" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "S" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX,
                          startingY - 1,
                          treasureX,
                          treasureY,
                          path + "S",
                          "S",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "S")
            {
                MoveRobot(startingX,
                          startingY - 1,
                          treasureX,
                          treasureY,
                          path + "S",
                          "S",
                          1,
                          pathVector);
            }
        }
        else if (startingY + treasureY > 0)
        {
            if (lastMove == "N" && numMovesDirection == MaxStepsDir)
            {

            }
            else if (lastMove == "N" && 
                     (numMovesDirection < MaxStepsDir || 
                      numMovesDirection > MaxStepsDir))
            {
                MoveRobot(startingX,
                          startingY + 1,
                          treasureX,
                          treasureY,
                          path + "N",
                          "N",
                          numMovesDirection + 1,
                          pathVector);
            }
            else if (lastMove != "N")
            {
                MoveRobot(startingX,
                          startingY + 1,
                          treasureX,
                          treasureY,
                          path + "N",
                          "N",
                          1,
                          pathVector);
            }
        }
    }
}

Я знаю, что «возврат» в первом операторе if останавливает рекурсию, но я не знаю, где ещеЯ бы закончил рекурсию, когда все 10 кратчайших путей в приведенном мной примере найдены и напечатаны.Как это только печатает EENNN.Пожалуйста, игнорируйте операторы if, которые говорят: «if (lastMove ==« W »&& numMovesDirection == MaxStepsDir)», я планирую заполнить их позже, чтобы заставить работать другую часть программы.Любая помощь в этом очень ценится!

1 Ответ

0 голосов
/ 04 февраля 2019

Разобрался сам.Извините, если я потратил на это время.С моей стороны было как принципиальное недопонимание рекурсии, так и небольшая ошибка в коде.Я не осознавал, что рекурсия автоматически распечатывает все кратчайшие пути, возвращаясь назад и идя по другим путям.Ошибка в моем коде, которая препятствовала этому, заключалась в том, что в большом «else» в конце моего кода я случайно добавил «else if (initialY - treasureY> 0)».Это должно просто сказать «если (начальный Y - treasureY> 0)», так как весь смысл этого большого блока кода else состоит в том, чтобы изменить и координату x, и координату y, если ни один из них не находится в правильном положении, и поместить else, если есть препятствиетот.Как только это, если if изменяется на if, он печатает все десять кратчайших путей для примера, который я привел.

...