Рекурсивный поиск пути до результата деления 1

Question

Я пытаюсь решить упражнение в рекурсии, которое выглядит следующим образом. Скажем, у вас есть матрица nxm с целыми числами, как это (просто пример):

1 1 1 5 2 2 3 5 2 1 3 1 1 1 5 1 1 5 1 1

Я хочу найти путь (начиная с любого места), который, учитывая число n, каждый шаг n изменяется на n / (number_at_that_position) и путь останавливается, когда n = 1.

Я не ищу все пути, я просто ищу путь. Поэтому, если вы используете символы для отображения пути, вы получите матрицу

> > V - * - - V > ^ - - V ^ - - - > ^ -

Где «>» означает шаг вправо, «<» означает шаг влево, «^» - это шаг вверх, а «V» - это шаг вниз. Как только n становится 1, мы вставляем '*', чтобы сказать, что путь закончился. Самое важное: путь должен быть непрерывным, и вы не можете посетить место, которое посетили раньше. Еще более важно: функция, которая находит путь, ДОЛЖНА быть рекурсивной. Если путь не найден, код завершается с сообщением о том, что путь не найден. </p>

До сих пор я придумал следующий код для поиска пути. Я использовал идеи из разных мест, но одно из них это Рекурсивное нахождение пути через лабиринт c ++

bool path_print(vector<vector<int> > &P,  size_t line, size_t col, vector<vector<char> > &A, int n) {
  if (line < 0 || line > P.size() || col < 0 || col > P[0].size()) {
    return false;
  }
  if (A[line][col] != '-') {
    return false;
  }
  if (n == 1) {
    A[line][col] = '*';
    return false;
  }
  printf("n = %d, line = %zu, col = %zu\n", n, line, col);
  n = n/P[line][col];
  if (path_print(P, line, col+1, A, n) == true){
    A[line][col] = '>';
    return true;
  } else if (path_print(P, line-1, col, A, n) == true) {
    A[line][col] = '^';
    return true;
  } else if (path_print(P, line+1, col, A, n) == true){
    A[line][col] = 'V';
    return true;
  } else if (path_print(P, line, col-1, A, n) == true){
    A[line][col] = '<';
    return true;
  } 
  return true;
}

P - вектор, содержащий значения A является вектором char, который хранит путь n - фактическое число, которое вы проверяете

Я работал над этим некоторое время и застрял. Этот код не работает должным образом. Любые предложения или помощь будет принята с благодарностью. Заранее спасибо

Answer 1

В вашем коде:

if (line < 0 || line > P.size() || col < 0 || col > P[0].size())

неверно, потому что:

• , что позволяет использовать индексы P.size() и P[0].size(), висходный код ссылки, с которой сделаны сравнения size - 1
• строка - это size_t, поэтому делать line < 0 не имеет смысла, то же самое для col

может быть:

bool path_print(vector<vector<int> > &P,  int line, int col, vector<vector<char> > &A, int n) {
   if (line < 0 || line >= (int) P.size() || col < 0 || col >= (int) P[0].size())

или для проверки col и line , прежде чем делать + 1 или -1 на них в рекурсивном вызове, чтобы избежать каких-либо проблем, включая переполнение.

---

Но этого недостаточно для решения вашей проблемы, потому что другие ваши изменения из кодассылка неверна:

• вы изменяете ячейку после рекурсивных вызовов, а не до
• вы не сбрасываете ячейку в '-' после
• когда вы найдете выход (в вашем случае n равен 1) вы возвращаете false вместо true , поэтому вы продолжаете поиск, и выпроверьте значение n слишком позднотер другой ход
• в конце возвращаемой функции true вместо false

---

Обратите внимание, что этобесполезно продолжать поиск, пока n равно 0 после деления

---

Для записи if (f() == true) является избыточным, if (f()) достаточно

---

AРешение, изменяющее ваш код:

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

bool searchPath(const vector<vector<int> > & P, 
                size_t line, size_t col,
                vector<vector<char> > &A,
                int n) {
  if (A[line][col] != '-') {
    return false;
  }

  n = n/P[line][col];

  if (n == 1) {
    A[line][col] = '*';
    return true;
  }
  if (n == 0)
    return false;

  A[line][col] = '>';
  if ((col != (P[0].size() - 1)) && searchPath(P, line, col+1, A, n)) {
    return true;
  } 

  A[line][col] = '^';
  if ((line != 0) && searchPath(P, line-1, col, A, n)) {
    return true;
  }

  A[line][col] = 'V';
  if ((line != (P.size() - 1)) && searchPath(P, line+1, col, A, n)){
    return true;
  }

  A[line][col] = '<';
  if ((col != 0) && searchPath(P, line, col-1, A, n)){
    return true;
  } 

  A[line][col] = '-';
  return false;
}

int main(int argc, char ** argv)
{
  vector<vector<int> > P;
  vector<vector<char> > A;

  // fill vectors

  int lines, columns;

  cout << "number of lines and columns : ";

  if (!((cin >> lines) && (cin >> columns) && (lines > 0) && (columns > 0))) {
    cout << "invalid sizes" << endl;
    return -1;
  }

  P.resize(lines);
  A.resize(lines);

  cout << "enter maze" << endl;
  for (int i = 0; i != lines; ++i) {
    P[i].resize(columns);
    A[i].resize(columns);
    for (int j = 0; j != columns; ++j) {
      int v;

      if (!(cin >> v) || (v < 1)) {
        cout << "invalid input : " << v << endl;
        return -1;
      }
      P[i][j] = v;
      A[i][j] = '-';
    }
  }

  int n;

  cout << "enter n : ";

  if (!(cin >> n) || (n <= 0)) {
    cout << "invalid value of n" << endl;
    return -1;
  }

  // search a way from all cells
  for (size_t l = 0; l != (size_t) lines; ++l) {
    for (size_t c = 0; c != (size_t) columns; ++c) {
      if (searchPath(P, l, c, A, n)) {
        // found
        cout << "found from cell line " << l << " column " << c << endl;

        for (l = 0; l != (size_t) lines; ++l) {
          for (c = 0; c != (size_t) columns; ++c) {
            cout << A[l][c] << ' ';
          }
          cout << endl;
        }

        return 0;
      }
    }
  }

  cout << "no solution" << endl;
  return 0;
}

Примеры:

number of lines and columns : 4 5
enter maze
1 1 1 5 2
2 3 5 2 1
3 1 1 1 5
1 1 5 1 1
enter n : 200
found from cell line 0 column 0
> > > > V 
- * - - V 
- ^ < < V 
- - - ^ < 

number of lines and columns : 4 5
enter maze
1 1 1 5 2
2 3 5 2 1
3 1 1 1 5
1 1 5 1 1
enter n : 999999
no solution