На прошлом занятии мы рассмотрели структуру данных Стек, а также одно из его применений на примере поиска в глубину. Сегодня обратим свое внимание в сторону такой структуры данных, как Очередь. Как и раньше на текущем этапе мы не будем разбирать внутреннюю реализацию очереди, а рассмотрим уже готовую STL-скую. Справочную информацию можно почитать здесь.
Одним из самых ярких применений очереди можно пронаблюдать на примере алгоритма Поиска в ширину (BFS).
Задача "Путешествие шахматного коня" (Поиск в ширину)
Технические моменты:
Для того, чтобы было удобно перебирать все соседние клетки, достижимые из текущей, шагом коня, предлагаю воспользоваться массивом движений:
- int moveX[8] = {-2,-2,-1,-1,1,1,2,2};
- int moveY[8] = {-1,1,-2,2,-2,2,-1,1};
Основная идея:
Рассмотрим работу поиска в ширину пошагово на основе тестового примера (A5 C2). Для более удобного представления шахматной доски в виде матрицы будет считать буквенную часть координаты номером строки, а числовую – номером столбца.
