Найти изолированные группы блоков в сетке

Question

У меня есть сетка «блоков» (в виде 2D-массива, может быть 5 * 5, 17 * 17 или что-то еще), где я могу добавлять или удалять блоки по желанию, за исключением для одного в центре, который должен всегда оставаться там.

Я могу разместить блоки, если у них есть соседний сосед: справа/слева/вверх/вниз (по крайней мере один из них).

Удаляя некоторые блоки, он может покидать другие блоки, изолированные без «соединения» с центральным блоком, и я хочу избежать этого.

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

Я использую C++, но это не должно иметь никакого значения.

Answer 1

Вам необходимо найти подключенные компоненты, используя DFS/BFS. Создайте исходный граф и добавьте новые блоки, вы можете добавить новые ребра или удалить блоки, которые вы можете удалить. Когда вы удаляете блок, временно удалите эти ребра в графе и проверьте, не вызывает ли это отключение двух частей графика. Это просто, выполните DFS снова. Если он не отключается, вы можете удалить этот блок.

DFS - это всего лишь около 8 строк для реализации, а для небольших наборов данных это изящно.