Тёмные острова
Фотограф хочет понять, как устроены тени на снимке. Он выбирает порог яркости t и считает тёмными все пиксели с яркостью не больше t. Тёмные пиксели, соседние по стороне, образуют острова. При пороге 0 островов немного — только самые чёрные точки. Порог растёт, тёмного становится больше, острова появляются и сливаются, а при пороге 255 весь снимок — один остров. Посчитайте число островов для каждого порога от 0 до 255.
Три теста — фотографии автора сайта шириной 120 пикселей. Яркость пикселя в них — (299·R + 587·G + 114·B + 500) div 1000, целочисленная яркость по стандарту Rec. 601.
Вход
В первой строке высота h и ширина w снимка (1 ≤ h·w ≤ 100 000). Дальше h строк по w целых чисел от 0 до 255 — яркости пикселей.
Выход
Одна строка из 256 чисел через пробел: число островов при порогах 0, 1, …, 255. Пиксели — соседи, если у них общая сторона; по диагонали пиксели не соседи.
Примеры
Пример 1
4 5 9 9 1 9 9 9 3 2 3 9 9 9 9 9 9 0 9 4 9 0
2 3 3 3 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Пример 2
3 3 0 5 0 5 0 5 0 5 0
5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитать острова для одного порога легко — обходом в ширину или в глубину. Но порогов 256, и каждый обход проходит весь снимок. Чем отличается картина при пороге t + 1 от картины при t?
2Подсказка 2
При переходе к порогу t + 1 тёмные пиксели не исчезают — добавляются новые, ровно те, у которых яркость t + 1. Острова только рождаются и сливаются. Какая структура следит за такими слияниями?
3Идея
Пройти пороги по возрастанию и добавлять пиксели в систему непересекающихся множеств. Новый тёмный пиксель — новый остров: счётчик плюс один. Затем он сливается с каждым тёмным соседом, и каждое удачное слияние — минус один остров. После всех пикселей очередной яркости счётчик и есть ответ для этого порога.
4Разбор
Сначала разложим пиксели по яркости — 256 списков, сортировка подсчётом за O(h·w). Пиксель (r, c) — элемент r·w + c; его соседи сверху и снизу отстоят на w, слева и справа — на единицу, если не выходят за край строки. Массив dark отмечает, какие пиксели уже тёмные: сливать новый пиксель можно только с ними.
Порядок добавления внутри одной яркости не важен: к концу её обработки все пиксели этой яркости добавлены, и острова — те же, что при честном обходе. Обратите внимание, что новые пиксели одной яркости могут сливаться и друг с другом — их проверка соседей это учитывает, ведь dark ставится до проверки.
Так же работает функция measure.label в scikit-image и алгоритм Хошена — Копельмана из физики перколяции — только им нужен один порог, а нам все сразу, и система непересекающихся множеств даёт их одним проходом.
4+Решение
5Сложность
Каждый пиксель добавляется один раз и пробует не больше четырёх слияний: O(N α(N)) для N = h·w пикселей, плюс 256 на вывод. Обход для каждого порога — O(256·N).
6Типичные ошибки
- Обход заново для каждого порога. Ответы верные, но на снимке в 90 000 пикселей это 23 миллиона шагов обхода — в шестом тесте не уложиться.
- Соседи через край строки. Пиксели r·w + w − 1 и (r + 1)·w — соседи в массиве, но не на снимке: правый край одной строки и левый край следующей.
- Диагональные соседи. Во втором примере тёмные клетки с яркостью 0 касаются только углами, и при порогах от 0 до 4 это пять отдельных островов.
- Рекурсия. В последнем тесте один извилистый остров на 45 тысяч пикселей. Обход в глубину рекурсией упрётся в предел глубины, а рекурсивный
findбез слияния по размеру — тоже, если дерево успеет вытянуться.