Карточка Junior Матрицы обновлено
Матрица как граф
Вопрос
Почему задачи на сетку сводятся к графам?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Каждая клетка вершина, соседи по сторонам рёбра. Острова, кратчайший путь в лабиринте, заливка решаются BFS или DFS за O(R · C).
Ответ
Каждая клетка вершина, соседи по сторонам рёбра. Острова, кратчайший путь в лабиринте, заливка решаются BFS или DFS за O(R · C). Посещённые помечают в отдельной матрице или прямо в сетке.
Разбор
Каждая клетка вершина, соседи по сторонам рёбра. Острова, кратчайший путь в лабиринте, заливка решаются BFS или DFS за O(R · C). Посещённые помечают в отдельной матрице или прямо в сетке.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.