Карта местности кластера не пересекается рекой через карту / матрицу?
У меня есть простая матрица (матрица, которая представляет карту местности в 2d игре, содержит символы ASCII, например, «m» для горы, «v» для долины, «r» для реки), а на карте может быть одна или ни одна река. Река может течь из любой позиции от матрицы к любой (и всегда разделять карту на две отдельные части => источник реки на карте невозможен, всегда входите в один конец и существует в другом). Как разделить матрицу / карту местности на две группы, если есть река?
пример местности
v v v v v v v v r v v v v v
v v v v v m m m r m m m m m
v v v v v m m r r m m m m m
m m v m m m m r r m m m v v
v v v v v v r r v v v v v v
здесь я должен получить левую группу и правую группу координат, которые не являются рекой.
Решение
Вы должны попробовать поискать алгоритм Fill.
http://en.wikipedia.org/wiki/Flood_fill
По сути, вы хотите выбрать точку, которой нет в реке, запустите алгоритм заливки, который даст вам набор точек, связанных с начальной точкой. Таким образом, теперь у вас есть одна часть, и теперь найти ее довольно просто.
Другие решения
Ваша карта вызывает график:
- есть одна вершина для каждой ячейки карты
- две вершины связаны, если они смежные а также ни один из них не является ‘r’
После построения графа вы можете запустить алгоритм обхода графа, например: поиск в ширину (BFS) или поиск в глубину (DFS), чтобы найти подключенные компоненты графика.
Я бы рекомендовал использовать BFS, потому что если карта большая, то DFS может привести к переполнению стека (если используется его рекурсивная реализация).
Вы захотите запускать BFS только на узлах, отличных от ‘r’, чтобы в итоге вы получили два подключенных компонента.