|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 05-3. Таблица.
(Разбор)
Пусть клетки таблицы будут вершинами графа. Ребрами соединим клетки, имеющие общую сторону. Нетрудно убедиться, что расстояние между клетками таблицы равно расстоянию между соответсвующими им вершинами в графе. Обойдем граф в ширину, в начале добавив в очередь все вершины, соответствующие клеткам, содержащим 1. Полученные расстояния и будут ответом на поставленную задачу.
Как и в предыдущей задаче, граф не нужно хранить в памяти компьютера.