Завдання з біології#149

Завдання з біології (Розбір)

Уважно прочитаємо означення сусідства: два білі пікселі сусідні, якщо вони лежать в одному рядку або одному стовпці і всі пікселі між ними теж білі. Тобто вони мають належати одному суцільному білому відрізку.

Звідси задача розпадається на просте підрахункове спостереження. Розглянемо максимальний горизонтальний ланцюжок білих пікселів довжини (обмежений чорними пікселями або краєм зображення). Будь-які два пікселі цього ланцюжка сусідні між собою, бо між ними лише білі. А пікселі з різних ланцюжків сусідніми бути не можуть — їх розділяє щонайменше один чорний. Отже, такий ланцюжок дає рівно

\binom{L}{2} = \frac{L(L-1)}{2}

пар.

Те саме справедливо для вертикальних ланцюжків.

Отже, розв'язок такий: проходимо всі рядки, знаходимо максимальні ланцюжки з символів . і додаємо \frac{L(L-1)}{2} за кожен; потім те саме робимо по стовпцях.

Подвійного врахування не буде: горизонтальна пара лежить в одному рядку, вертикальна — в одному стовпці, а обидві умови одночасно виконувались би лише для двох однакових пікселів, чого бути не може (пікселі різні).

Зручна реалізація — один прохід із лічильником поточної довжини: на . збільшуємо його, на # додаємо внесок і обнуляємо. Не забудьте додати внесок і в кінці кожного рядка та стовпця.

Складність — . Відповідь сягає порядку N M^2, тому накопичуйте її у 64-бітному типі.