Автор задачи: Артемий Блинов, разработчик: Егор Юлин
Будем решать задачу следующим образом:
Заведём СНМ, в котором будем хранить следующую информацию: количество ячеек в множестве, максимальную высоту $$$d_{i,j}$$$, соприкасается ли хотя бы одна из ячеек с границей.
Отсортируем ячейки по высоте $$$h_{i,j}$$$ и будем обрабатывать их по возрастанию высот. Пусть мы рассматриваем ячейку $$$(i,j)$$$. Рассмотрим все соседние для нее, обозначим такие ячейки за $$$(i',j')$$$. Для них верно, что $$$|i-i'|+|j-j'|=1$$$. Если соседняя еще не была обработана то пропустим её.
Теперь есть два случая:
После обработки ячейки $$$(i,j)$$$ ее нужно объединить со всеми ячейками $$$(i',j')$$$.
В сумме решение потребует $$$\mathcal{O}(nm \log{nm})$$$ времени как минимум на сортировку по высоте. Работа с СНМ займет асимптотически меньше времени.