Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Листинг 2.15. 
Maze.java (продолжение)
public 
List successors(MazeLocation ml) {
List locations = 
new 
ArrayList<>();
if 
(ml.row + 1 < rows && grid[ml.row + 1][ml.column] != Cell.
BLOCKED
) {
locations.add(
new 
MazeLocation(ml.row + 1, ml.column));
}
if 
(ml.row — 1 >= 0 && grid[ml.row — 1][ml.column] != Cell.
BLOCKED
) {
locations.add(
new 
MazeLocation(ml.row — 1, ml.column));
}
if 
(ml.column + 1 < columns && grid[ml.row][ml.column + 1] != Cell.
BLOCKED
) {
locations.add(
new 
MazeLocation(ml.row, ml.column + 1));
}
if 
(ml.column — 1 >= 0 && grid[ml.row][ml.column — 1] != Cell.
BLOCKED
) {
locations.add(
new 
MazeLocation(ml.row, ml.column — 1));
}
return 
locations;
}

---

62
Глава 2.
Задачи поиска
Функция.
successors()
.просто.проверяет.верхнюю,.нижнюю,.правую.и.левую.
смежные.по.отношению.к.
MazeLocation
.ячейки.в.
Maze
,.чтобы.увидеть,.есть.ли.
там.пустые.места,.в.которые.можно.попасть.из.этой.ячейки..Также.это.позволяет.
избежать.проверки.ячеек.за.пределами.лабиринта..Все.возможные.обнаруженные.
MazeLocation
.помещаются.в.список,.который.в.итоге.возвращается.вызывающей.
функции..В.наших.алгоритмах.поиска.будем.использовать.два.предыдущих.метода.
2.2.3. Поиск в глубину
Поиск в глубину
.(depth-first.search,.DFS).—.это.именно.то,.чего.можно.ожидать,.
судя.по.названию:.поиск,.который.заходит.настолько.глубоко,.насколько.воз-
можно,.прежде.чем.вернуться.к.последней.точке.принятия.решения.в.случае,.
если.процесс.зайдет.в.тупик..Мы.реализуем.параметризованный.поиск.в.глубину,.
который.позволяет.решить.задачу.прохода.по.лабиринту..Этот.поиск.можно.ис-
пользовать.для.решения.и.других.задач..Развитие.поиска.по.лабиринту.в.глубину.
проиллюстрировано.на.рис..2.4.
Рис. 2.4.
Поиск в глубину проходит по непрерывному пути вглубь, пока не дойдет до 
препятствия и не будет вынужден вернуться к последней точке принятия решения

---

2.2. Прохождение лабиринта