Лабиринт решатель записи пути назад

Question

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

Как я могу предотвратить это в моей текущей реализации ниже:

int dir = 4;

bool visited[Max_Maze][Max_Maze][dir];


for (row = 0; row < size; ++ row)
{
  for (col = 0; col < size; ++ col)
  {
    for (dir = 0; dir < 4; ++ dir)
    {
      visited[row][col][dir]=false;
    }
  }
}

bool notSolved = true;
int path = 0;
row = 0;
col = 0;

rowStack.push(row);
colStack.push(col);

while (notSolved)
{

  //from perspective of person looking at maze on screen
  if (((row-1)>=0)&&(maze[row - 1][col] == 0)&&(visited[row][col][0]==false))
  {
    // if that space is not out of bounds and if you can go up
    // and you have not gone in that direction yet, go up
    visited[row][col][0] = true; 
    row--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col+1)<size)&&(maze[row][col + 1] == 0)&&(visited[row][col][1]==false))
  {
    //else if you can go right etc., go right
    visited[row][col][1] = true;
    col++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((row+1)<size)&&(maze[row + 1][col] == 0)&&(visited[row][col][2]==false))
  {
    //else if you can go down etc., go down
    visited[row][col][2] = true;
    row++;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else if (((col-1)>=0)&&(maze[row][col - 1] == 0)&&(visited[row][col][3]==false))
  {
    //else if you can go left etc., go left
    visited[row][col][3] = true;
    col--;
    rowStack.push(row);
    colStack.push(col);
    path++;
  }
  else
  {
    //if stuck
    if (path == 0)
    {
      cout << "No Solution Path" << endl;
      notSolved = false;
    }
    else
    {
      rowStack.pop();
      colStack.pop();
      row = rowStack.top();
      col = colStack.top();
      path--;
    }
  }

  if((maze[row][col] == 0) && (row == (size - 1) && col == (size - 1)))
  {
    //if we reached an exit
    cout << "Solution Path:(in reverse)" << endl;
    for (int i = 0; i <= path; i++)
    {
      cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
      rowStack.pop();
      colStack.pop();
    }
    notSolved = false;
  }
}

Требуется простое исправление или полная реструктуризация?

Answer 1

Когда решатель попадает прямо в этот тупик, он записывает, что он "посетил прямо из (R, C)", потому что ваш посещенный массив является трехмерным.Но он никогда не записывает, что он "посетил слева от (R, C + 1)".Таким образом, он считает, что нормально перемещаться в одну и ту же позицию дважды , если только он не делает одно и то же движение дважды (чего не происходит, так как он движется влево, когда возвращается, а не вправо).

Похоже, что он будет работать нормально, как если бы вы изменили посещаемость на 2-мерный массив и записывали только позиции , а не движения.Затем каждый квадрат, который вы посетили прежде, блокирует дальнейшее движение, но это нормально, потому что, если правильное решение требует возврата к этому квадрату, вы в конечном итоге попадете в другой случай, достаточный, чтобы вернуться к нему, и оттуда три должны быть никогда.посетил площадь, чтобы исследовать.

Answer 2

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

boolean dfs (State s) {
    if (end_state(s)) {
        return true;
    }

    vector<option_t> options = generate_moves(s);
    for (vector<option_t>::iterator it = options.begin();
         it != options.end(); it++) {
        make_move(s, it);
        boolean found = dfs(s);
        if (found) {
            cout << s << endl;
        }
        undo_move(s, it);
        if (found) return true;
    }
    return false;
}

Как видите, это будет работать до тех пор, пока вы можете создать:

1. некое классовое состояние, которое содержит ваше текущее состояние лабиринта
2. функция end_state, которая знает, когда State находится в решении
3. функция generate_moves, которая может найти все опции для текущего состояния
4. make_move, который может применить ход против вашего состояния
5. undo_move, который может отменить движение против состояния
6. вы определяете option_t так, чтобы он представлял опцию перемещения
7. определение оператора << для состояния </li>

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