Задача 12.
Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?
Пример. Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.
МОДИФИКАЦИЯ. То же, но перед удалением клеток лист склеили в цилиндр высотой N.
|
Решение задачи 12.
Идея решения состоит в последовательном определении множества клеток, принадлежащих тому же куску, что и некоторая фиксированная клетка.
Начиная с некоторой непомеченной клетки (начальной), которая помечается, помечаются все клетки, имеющие с ней общую сторону. Затем, используя вновь помеченные клетки, помечается множество клеток, имеющих с ними общую сторону и т.д., пока на некоторой итерации не будет помечено ни одной новой клетки. Множество клеток, помеченных таким образом, и составляет единый кусок листа максимального размера.
Для подсчета общего количества кусков необходимо подсчитать количество клеток, выбранных в качестве начальных. Новая начальная клетка выбирается из множества клеток, не помеченных на предыдущих итерациях. Для хранения вновь помеченных клеток можно использовать очередь или стек, а пометку клеток можно проводить в матрице размера N*M.
|
