У вас не так много решений: в основном, исследование лабиринта без цикла похоже на выполнение поиска в глубину в дереве покрытий, где каждое пересечение является узлом.
Вы можете построить дерево по ходу дела и использовать эту информацию для обхода, но это будет не очень эффективно.
Обычный метод поиска в глубину состоит в том, чтобы поместить все проверяемые узлы в стек, извлечь один и снова поместить, пока не будет достигнута цель. Но у вас складывается множество узлов, и как только вы нашли целевой узел, вы не можете использовать стек, чтобы узнать, по какому пути вы шли, а это означает, что вам нужно хранить эту информацию в другом месте.
Вероятно, лучше сохранить решение стека и пометить узлы в вашем стеке, чтобы указать ветвь, и какое направление (т. е. какое поддерево) ветви было < em>исследовано (или какие пути остались). Если вы всегда выполняете исследование в одном и том же порядке, этот тег может быть просто числом:
- 0 слева
- 1 для переда
- 2 справа
- 3 для возврата
или еще лучше перечисление.
Когда тупик найден, просто раскрутите стек, пока не найдете один из этих узлов, и попробуйте новое направление. Если испробованы все направления, другими словами, если направления не осталось, раскручивайтесь снова.
enum Branch {
LEFT,
FORWARD,
RIGHT,
BACKTRACK
};
struct BacktrackException{
};
template <typename MazeMove>
struct StackNode {
MazeMove move;
Branch branch;
StackNode(MazeMove m): move(m), branch(LEFT) {}
MazeMove nextBranch(){
switch(branch){
case LEFT:
if (move.can_left()){
branch = FORWARD;
return move.left();
}
case FORWARD:
if (move.can_forward()){
branch = RIGHT;
return move.forward();
}
case RIGHT:
if (move.can_right()){
branch = BACKTRACK;
return move.right();
}
default:
throw BacktrackException();
}
}
};
Приведенный выше код предоставляет оболочку для возможного класса MazeMove, используемого со стеком, который отслеживает предпринятое направление. Метод nextBranch возвращает следующий возможный ход или выдает исключение.
Преимущество в том, что ваш стек не будет уничтожен непроверенными ходами. Вы нажимаете StackNode каждый раз, когда достигаете новой позиции, и раскручиваете ее, когда все ее варианты проверены. Когда вы доберетесь до выхода из лабиринта, ваш стек будет содержать только необходимые ходы.
person
didierc
schedule
20.04.2013
