Поиск карты шестиугольника, если некоторые сетки окружены алгоритмом

Question

Я создаю простую математическую игру в геометрии шестиугольника через Unity.На самом деле речь идет не об Unity.

Я заимствую Image у https://catlikecoding.com/unity/tutorials/,, чтобы проиллюстрировать проблему, он довольно большой, поэтому я поместил его в ссылку.

---

Фон

То же, что и в учебнике по приведенной ссылке, я использую массив для сохранения данных, чтобы упростить его, он выглядит так:

[      0, 0, 0, 0,    
        0, 0, 0, 0,
       0, 0, 0, 0,
        0, 0, 0, 0,
       0, 0, 0, 0      ]

Моя цель

Проверить, окружена ли одна или несколько сеток сеткой другого типа.

Определение

Окружен означает для сетки или группы связанных сеток, все соседи находятся в разных флагах из них.

Например,

[      0, 1, 1, 0,    
        1, 0, 1, 0,
       0, 1, 1, 0,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

//Should become

[      0, 1, 1, 0,    
        1, 1, 1, 0,
       0, 1, 1, 0,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

Это довольно легкодля этого случая мне даже не нужен алгоритм, так как я могу создать сетку со ссылкой на ее соседа, например

class grid{
    grid[] neighbor;
    int flag; //0 or 1
}

Итак, когда мне нужно проверить, окружена ли сетка, мне просто нужнозацикливать его neighbor.

---

Проблема

Однако этот метод становится утомительным в следующем случае

[      0, 1, 1, 1,     
        1, 0, 0, 1,
       0, 1, 1, 1,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

Итак, мне также нужно проверить соседа его соседа, например,

foreach (grid i in neighbor){
   bool is_surrounded = false;
   if (grid.flag == 1) {
       //Good
   } else {
       //Check its neighbor, if every neighbor except i is 1, then return True. 
   }
}

Он отлично работает для 2, но что, если есть 3 пустых сетки?Рекурсия не в порядке, например, когда сетка не окружена, как

[      0, 1, 1, 1,     
        1, 0, 0, 1,
       0, 1, 0, 1,
        0, 0, 0, 0,
       0, 0, 0, 0       ]

, тогда я зациклю всю карту для проверки около 8 ^ n раз.

---

Вопрос

Я думаю, что есть более умный метод, который я не осознавал, я приветствую любой вид / язык ответа или даже просто идею.Конечно, я буду щедро вознагражден за работу и объяснение.

Спасибо.

Answer 1

Вы идете об этом задом наперед.Ваша логика кодирования выглядит хорошо, но переверните логику.

Для каждого 1 существующего проверьте его на предмет возможных других 1.Если вы вернетесь через любой путь из 1 (от), что в первую 1 (до), что в первую 1, то вы нашли замкнутый цикл.Найдите направление, откуда вернулся путь, чтобы вернуться к первому 1, а затем это место внутри цикла.Затем, если вас не интересуют какие-либо более глубокие циклы, отметьте все, что находится внутри (как 1, так и 0) этого цикла, как удаленные из дальнейшего поиска.Завершите поиск и затем после того, как поиск будет завершен, и только после того, как поиск будет завершен, отметьте все внутри циклов как 1 (если это то, что вы хотите).Таким образом, если у вас есть циклы рядом с циклами, вы не будете перезапускать снова и снова.

Для подциклов: рассматривайте все 1 как потенциальное начало цикла.Если вы вернетесь к любым предыдущим единицам, то найдите, в каком направлении они пришли (по пути возврата) и посчитаете, что внутри цикла.

Когда все это сделано, и вы нашли петли, затем выполнитеваши изменения.Не беспокойтесь, если петли имеют нулевое внутреннее положение, так как 0 является допустимым размером, просто сделайте все возможные изменения внутренних частей петли, как вы решите.

Спасибо.

B Lean

Answer 2

Сначала нужно сделать строгое определение - какой регион называется «окруженным».Возможно, возможный подход - ячейки без свободного пути к внешнему краю карты.

Чтобы проверить этот способ - используйте любой простой алгоритм обхода - например, DFS (алгоритмы поиска пути выглядят здесь излишне - им нужна конечная точка)

Что касается рекурсии - вам нужно пометить видимые ячейки, чтобы избежать перепроверки. Существуют заливка алгоритмов без рекурсии и с хорошей сложностью.