Это вдохновлено алгоритмом Крускала для создания лабиринта.
Я определяю окрестность квадрата как его 8 окружающих квадратов, включая внешнюю часть сетки (окрестность углового квадрата - это 3 окружающих его квадрата плюс внешняя сторона, поэтому всего 4 «квадрата»).
Распределите единицы по наборам так, чтобы любые две соседние единицы принадлежали одному и тому же набору. Рассматривайте внешнюю часть сетки как одну большую единицу (что означает, что она содержится в первом наборе). При добавлении 1 вам нужно только проверить его соседей.
Ниже приведены все возможные случаи. Чтобы упростить визуализацию, я буду нумеровать наборы, начиная с 1, и использовать номер набора вместо 1 в каждом квадрате, который содержит 1. Внешняя сторона принадлежит набору с номером 1. Вы также можете использовать это, чтобы упростить реализация. Скобки указывают на вновь поставленную 1.
Если у новой 1 нет соседней 1, то она принадлежит новому набору.
0 0 0 0 0
0 2 0 0 0
0 0 0[3]0
0 0 0 0 0
0 0 1 0 0
Если у него есть одна соседняя 1, то он принадлежит тому же множеству.
0 0 0 0 0
0 2 0 0 0
0 0[2]0 0
0 0 0 0 0
0 0 1 0 0
Если у него есть несколько соседних единиц, и все соседи, принадлежащие к одному и тому же набору, являются прямыми соседями, то вы можете объединить наборы, и новая единица будет принадлежать результирующему набору. Нет необходимости проверять отключение.
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 0[3]1 0 -> 0 0[1]1 0
0 0 1 1 0 0 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 2 0 1 0 -> 0 1 0 1 0
[3]0 0 1 0 [1]0 0 1 0
1 1 1 0 0 1 1 1 0 0
Если у него есть несколько соседних единиц одного и того же набора, но не все они являются прямыми соседями, то у вас есть отключение.
0 0 0 0 0 0 0 0 0 0 <- first group of 0s
0 2 0 0 0 0 1 0 0 0
0 0[3]1 0 -> 0 0[1]1 0
0 1 0 1 1 0 1 0 1 1
1 0 0 0 0 1 0 0 0 0 <- second group of 0s
0 0 0 0 0 <- first group of 0s
0 0 1 0 0
0 1 0 1 1
[1]1 0 0 0
0 0 0 0 0 <- second group of 0s
0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 1 0 0 0
0 2 0 1 0 -> 0 1 0 1 0
[3]0 0 1 0 [1]0 0 1 0
0{1}1 0 0 lone 0 -> 0{1}1 0 0
В этом последнем примере 1, отмеченная {1}, и внешнее технически являются соседями, но не с точки зрения вновь размещенной 1.
В общем случае при удалении 1, у которого есть несколько соседних 1, нужно проверить, связаны ли они после удаления (например, запустив между ними поиск пути). Если нет, разделите их на разные наборы.
Если вы знаете, что все 0 связаны, то вы можете проверить локально: удаление 1 не приведет к разделению набора, к которому он принадлежит, если все его соседи являются прямыми соседями (однако будьте осторожны с внешними). Это произойдет, если в его окрестностях есть несколько «пробелов».
В особом случае, когда вы удаляете 1 только в порядке, обратном их добавлению, вы можете отслеживать, какие вновь добавленные 1 объединяют несколько наборов (и даже какие наборы в данный момент, если вам нужно). Они разделят свой набор, когда вы удалите их позже.
person
Nelfeal
schedule
07.08.2018
