지도에서 모든 포리스트 클러스터를 찾는 방법은 무엇입니까?

Question

지도에서 모든 포리스트 클러스터를 찾는 방법은 무엇입니까? (유형 열거 {강, 숲, 잔디, 힐}

class Cell{ 
    public: 
    Type type; 
    int x; 
    int y 
}; 

을하고 vector<Cell> grid 같은지도처럼 나는 간단한 클래스 세포가 있습니다. 목록이 동일한 클러스터에서 FOREST 세포를 포함하는 경우 누군가가 (나를 list<list<Cell>> clusters을 만들 산법 클러스터를 제안 할 수 up, down, left, right, up_right, up_left, down_left, down_right)? 모든 포리스트 클러스터를지도에서 찾아서 모든 단일 클러스터를

에 넣어야합니다.

Answer 1

알고리즘은 다소 단순하며 실제로 클러스터의 정확한 정의에 의존하지도 않습니다. 술어이 있다고 가정 해 보겠습니다. f0과 f1이 동일한 클러스터에있는 경우 true을 생성하는입니다. grid을 실행하고 숲을 찾으려면 모두해야합니다. f 셀이 포리스트 인 경우 각 알려진 포리스트에 대해 cluster(f, other)인지 확인합니다. cluster(f, other)이 true 인 경우 other 클러스터에 f을 추가합니다. 다른 클러스터의 다른 알려진 포리스트를 계속 확인합니다. cluster(f, c)에 대한 또 다른 클러스터의 다른 셀 c도 true을 찾으면 두 클러스터를 병합합니다 (std::list<Cell>::spice()).

Answer 2

I는 주석으로이를 넣어했지만, 물론 대답 할 수 있습니다

노조 찾기 알고리즘을 검색합니다. 경로 압축을 사용하면 나중에 구조를 살펴보고 각 루트에 대한 목록을 만들 수 있습니다. 적절한 목록에 셀을 추가하십시오.

링크 : 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에 다음 node.root 점의 경우.