Исключение полей с определенным состоянием из 2D массива; Игра жизни
У меня есть массив — 2D (в данном случае 100 x 100) с некоторыми состояниями, ограниченными в пределах границ, как показано на рисунке:
http://tinypic.com/view.php?pic=mimiw5&s = 5 # .UkK8WIamiBI
Каждая ячейка имеет свой собственный идентификатор (цвет, например, зеленый — это id = 1) и флаг isBorder (отмечен белым на рис., Если он истинный). То, что я пытаюсь сделать, это исключить набор ячеек с одним состоянием, ограниченным границами (зерно), чтобы я мог работать с каждым зерном отдельно, что означает, что мне нужно будет хранить все индексы для каждого зерна.
У кого-нибудь есть идеи, как это решить?
Решение
Теперь, когда я снова прочитал ваш вопрос … Алгоритм по сути такой же, как заполнение непрерывной области цветом. Наиболее распространенный способ сделать это — алгоритм BFS.
Просто начните с некоторой точки, в которой вы уверены, что она находится внутри текущей области, затем постепенно перемещайтесь в каждом направлении, выбирая пройденные поля и помещая их в vector,
// Редактировать: куча других идей, сделанных до того, как я понял вопрос.
Я могу представить себе алгоритм, работающий так:
vector<2dCoord> result = data.filter(DataType::Green);
for (2dCoord in result) {
// do some operations on data[2dCoord]
}
Реализация filter простым неоптимизированным способом будет сканировать весь массив и push_back сопоставление полей с вектором.
Если вам понадобятся более сложные запросы, прокси-объекты с ленивой оценкой могут творить чудеса:
data.filter(DataType::Green)
.filter_having_neighbours(DataType::Red)
.closest(/*first*/ 100, /*from*/ 2dCoord(x,y))
.apply([](DataField& field) {
// processing here
});
Другие решения
Других решений пока нет …