Заполните 2D-массив двумя разными номерами, но каждый номер должен быть размещен рядом с равным числом

Question

Я пытаюсь заполнить 2d-массив случайным образом с помощью 0s и 1s. Условие состоит в том, что каждый 1 должен быть «помещен» рядом с другим 1 вертикально или горизонтально, но не по диагонали.

http://prntscr.com/8nzl19 На снимке экрана вы видите 3 блока 1-го. Я хочу, чтобы они были «связаны», так что есть только один блок из 1s.

Есть ли какой-нибудь алгоритм или что-то в этом роде?

Answer 1

Поскольку тривиальный способ будет заполнять всю матрицу 1, я предполагаю, что вы хотите, чтобы минимальное число 0 было повернуто на 1.

Вот такой подход, который вы можете использовать:

• Найти все компоненты 1-й в матрице. (Дайте идентификатор им, позвоните им в виде A, B, C)
• Создайте копию матрицы.
• Выберите A. Сделайте BFS из всех «outpoints» A (в окружении, по меньшей мере, одного 0) другим подключенным компонентам (B, C). (BFS для кратчайших путей, конечно)
• Теперь в исходной матрице отметьте эти точки (скажем) 2.
• Повторите выше 2 шагов с B и C, а также. Вы можете заполнить исходную матрицу различными идентификаторами пути, если хотите. (3 для B, 4 для C и т. Д.)

Теперь рассмотрим связанные 1 как узлы и 2, 3 и т. Д. В графе как ребра. Вес края будет (очевидно) числом 2, 3 и т. Д. С одного узла на другой. Теперь вы можете сформировать MST этого графика, используя Prims или Kruskals algo.

Для матрицы (n * n) с k связанными компонентами 1, этот алгоритм принимает сложность O (k * n * n) + O (k * k).