Блог*

Мне прилетел случай, когда моё решение давало ответ, на единицу отличающийся от правильного. Это выглядело странно, потому что это не могло быть эффектом ошибки на единицу — в противном случае более простые примеры давали бы ту же ошибку. Я внимательно изучил пример, пытался его модифицировать и смотреть, как меняется ответ — и в итоге свёл его до минимального примера, ломающий мой алгоритм (для наглядности я обозначил воду точками и сушу решётками):

#..#
#.##
###.

Видите ли вы тут проблему? Я вот понял её благодаря своему отладочному выводу. Перерисуем этот пример, показав, какой номер территории приписывается каждой ячейке на очередном шаге:

0..1
0.21
000.

Во время обработки второй строки появляется территория с id = 2, которая сразу же становится частью территории с id = 1. После обработки второй строки связи между территориями выглядят следующим образом (стрелочкой показано отношение "является частью"):

[ 0 | 1 | 2 ]
      ^   |
      |   |
      \---/

С другой стороны, во время обработки третьей строки эта же территория становится частью территории с id = 0, и в итоге связи становятся такими:

[ 0 | 1 | 2 ]
  ^       |
  |       |
  \-------/

Здесь и кроется проблема: так как у территории с id = 1 нет никаких связей, она считается отдельным островом, а не частью острова, образованного территорией с id = 0. В итоге алгоритм ошибочно считает, что на карте два острова вместо одного. В принципе, тут примерно понятно, что нужно исправить: нужно менять не только связь у территории 2, но и у территории 1, на которую первая указывает...

...И тут я понял, что это как-то слишком походит по описанию на структуру непересекающихся множеств (disjoint sets aka union-find), про которую я когда-то читал в Википедии. В принципе, это структура данных напрашивалась с самого начала, но я рассчитывал, что смогу обойтись чем-то более простым. Ну что ж — делаю эту структуру (что, кстати, как ни странно, упростило код), фиксю пару мелких багов, отправляю на проверку — и — о чудо! — все тесты пройдены!

Все, кроме моего теста эффективности. На Leetcode после успешного решения задачи можно посмотреть, где твоё решение находится на гистограмме всех отправленных решений по времени. Оказывается, есть решения более быстрые. Заинтригованный, я открываю семпл из топового по времени решения. И что же я там вижу?

Depth first search.

Wikipedia

Disjoint-set data structure

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets.…

514 viewsedited 22:31