Где применяется
1. Задача
У тебя есть лабиринт на сетке. Одни клетки открыты, по ним можно ходить. Другие клетки это стены, на них наступать нельзя. Ты стоишь на одной клетке и хочешь попасть на другую. Ходить можно только вверх, вниз, влево или вправо, по одной клетке за ход. За какое наименьшее число шагов ты дойдёшь? А если стены отрезали цель, нужен ясный ответ «дойти нельзя».
В шаге 88 ты искал через BFS наименьшее число рёбер между узлами графа. Сетка тоже граф, только нарисованный квадратиками. Каждая открытая клетка это узел. У клетки до четырёх соседей: открытые клетки прямо над ней, под ней, слева и справа. Связь с таким соседом это ребро. Поэтому тот же поиск кольцами, который считал рёбра между станциями, теперь считает шаги по лабиринту. Новый алгоритм не нужен.
На сетках BFS встречается чаще всего: поиск пути по карте, робот, который едет по складу, инструмент «заливка» в графическом редакторе.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на сетке, где нужно наименьшее число шагов между клетками или расстояние от каждой клетки до ближайшей цели. Запусти поиск в ширину, где клетка это узел, а её открытые соседи это рёбра, и если источников несколько, положи их все в очередь в самом начале.
shortestSteps из урока, только цель это любая клетка на краю, кроме входа.
Тот же поиск в ширину с восемью направлениями вместо четырёх, и считаются клетки, а не шаги.
Положи все гнилые апельсины в очередь в самом начале, и число колец поиска в ширину будет ответом.
Начни сразу со всех нулей, и поиск в ширину запишет каждой клетке расстояние до ближайшего нуля.