Как найти все скопления леса на карте?
Как найти все скопления леса на карте?
У меня есть простая ячейка класса, как (Тип enum {RIVER, FOREST, GRASS, HILL}
class Cell{
public:
Type type;
int x;
int y
};
и карта как vector<Cell> grid, Может кто-нибудь предложить мне алгоритм создания list<list<Cell>> clusters где список содержит ячейки FOREST в одном и том же кластере (кластер представляет собой набор связанных ячеек — соединение может быть в восьми направлениях: вверх, вниз, влево, вправо, вверх_право, вверх_лефт, вниз_лефт, вниз_право)? Мне нужно найти все кластеры леса на карте и поместить каждый кластер в list<Cell>,
Решение
Алгоритм довольно прост, и на самом деле он даже не зависит от точного определения кластера. Скажем, у вас есть предикат cluster(f0, f1) который дает true если f0 а также f1 находятся в одном кластере. Все, что вам нужно сделать, это запустить хотя grid и найти лес. Если клетка f это лес, вы проверите, если cluster(f, other) для каждого известного леса. Если cluster(f, other) доходность true вы добавляете f в группу other, Вы продолжаете проверять другие известные леса в других кластерах: когда вы находите другую ячейку c в другом кластере для cluster(f, c) также дает trueСливаешь (std::list<Cell>::spice()) два кластера.
Другие решения
Я поместил это как комментарий, но могу также ответить:
Посмотрите на алгоритм поиска объединения. Используя сжатие пути, вы можете просто
потом пройтись по структуре и создать список для каждого корня,
добавляя ваши ячейки в соответствующий список, как вы идете.
Ссылка на сайт: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
Для всех ваших ячеек выполните объединение с ячейкой сверху и слева. Если вы хотите объединить диагонали, включите также диагональ в верхнем левом и правом верхнем углу).
Используйте версию union-find со сжатием пути, чтобы все узлы в кластере указывали на один корень. Затем все, что вам нужно сделать, — это пройтись по своей структуре (после выполнения всех объединений) и добавить узлы по мере продвижения. Псевдо (МОГ) код:
foreach node
Find(node) // this ensures path compression
if not clusters.hasList(node.root)
clusters.createList(node.root)
end
list <- clusters.getList(node.root)
list.append(node)
end
Выше предполагается, что если узел является корнем, то node.root указывает на node,