Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
|||
Строка 251:
Опишем алгоритм восстановления многоугольника по числам в клетках; из этого алгоритма в частности будет следовать, что решение всегда единственное.
Рассмотрим пример, изображенный на рис. 1.[[Изображение:Example.jpg|frame|Рис. 1]]
Будем восстанавливать границы многоугольника, двигаясь сверху вниз. Начнем с верхней строки. Посмотрим на одну из единиц, стоящую в верхней строке. Верхняя сторона этой клетки не может принадлежать границе многоугольника, поскольку, по условию, многоугольник лежит ''внутри ''листа бумаги. Боковые стороны этой клетки тоже не могут лежать на границе многоугольника, поскольку их концы выходят на границу листа. Следовательно, многоугольнику принадлежит нижняя сторона клетки, см. рис. 2.[[Изображение:Example.jpg|frame|Рис. 2]]
Мы отметили первые участки границы многоугольника. Уменьшим на 1 числа во всех клетках, границами которых эти участки являются (см. рис. 3).[[Изображение:Example.jpg|frame|Рис. 3]]
Итак, на первом шаге нашего алгоритма мы восстановили самые верхние горизонтальные стороны нашего многоугольника. Переходим к следующему шагу.
Рассмотрим концы нарисованных нами отрезков. Из каждой из этих точек должна выходить еще одна сторона нашего многоугольника, причем обязательно вниз (см. рис. 4).[[Изображение:Example.jpg|frame|Рис. 4]]
Как и на первом шаге, уменьшим соответствующие числа в клетках, прилежащих к нарисованным на этом шаге отрезкам. При этом некоторые числа уменьшаться сразу на 2, поскольку у некоторых клеток мы обвели две стороны (см. рис. 5)[[Изображение:Example.jpg|frame|Рис. 5]]
Итак, на втором шаге мы восстановили все вертикальные отрезки, обведенные во второй сверху строке. Переходим снова к горизонтальным отрезкам, спускаясь на одну клетку вниз.
Во второй строке осталась одна единица. Это означает, что нужно обвести отрезок под этой клеткой, и это единственный отрезок данной горизонтали, принадлежащий границе многоугольника. Обводя его, мы уменьшаем на 1 числа в прилежащих клетках (cм. рис. 6).[[Изображение:Example.jpg|frame|Рис. 6]]
В этой горизонтали остались две точки, их которых выходит пока только по одному отрезку. На следующем шаге из этих точек проводим вертикальные отрезки вниз, уменьшая числа в клетках (см. рис. 7).[[Изображение:Example.jpg|frame|Рис. 7]]
И, наконец, мы спускаемся еще ниже и по единицам в третей строке клеток восстанавливаем последний горизонтальный ряд (см. рис. 8).[[Изображение:Example.jpg|frame|Рис. 8]]
Итак, многоугольник восстановлен. Подведем итоги. Наш алгоритм восстанавливает отрезки сторон многоугольника последовательно, сверху вниз, поочередно восстанавливая горизонтальные и вертикальные отрезки каждой строки. При этом для проведения горизонтальных отрезков мы рассматриваем клетки верхней ненулевой строки, в которых стоят единицы, и обводим их нижние стороны, а для восстановления вертикальных отрезков мы ищем все врешины в предыдущей строке, из которых выходит только одна сторона.
| |||