2 차원 배열에서 동일한 셀 그룹을 계산하는 방법은 무엇입니까?

Question

여기에 (검은 사람 계산)의 예이다 :

입력 :

출력 :

5 4 // 5 groups (4 squares each) 
1 1 // 1 group containing 1 square 

지금, 나는에 대한 고통 스럽다보다 더 나은 아무것도 생각할 수 없다 되풀이. 재귀 방식으로 이러한 그룹을 확보 할 수 있습니까? 감사합니다.

Answer 1

모든 검은 색 사각형을 노드로 설정하십시오. 검은 사각형 사이의 연결 (사각형이 서로 옆에있는 경우)은 가장자리가됩니다.

이렇게하면 graph이됩니다.

그래프에서 DFS은 모든 그룹을 갖습니다. DFS는 본질적으로 재귀적임에 유의하십시오.

Answer 2

처음에는 각 셀을 "방문하지 않았습니다".

"방문하지 않은"검은 색 셀을 만날 때까지 셀을 반복합니다. 당신이 그 지점까지 쳤던 각각의 흰색 셀

검은 셀을 누르면 가능한 경우 모든 방향으로 "확장"합니다 ("floodfilling"과 유사). 가능한 한 확장하여 방문한 모든 셀을 "방문한"것으로 표시합니다. 그렇게 한 후에는 얼마나 많은 흑인 세포가 감염되었는지를 세고 그룹이 얼마나 큰지 알게됩니다. 그룹을 찾으면 다음 "방문하지 않은"검은 색 셀로 이동합니다.

Answer 3

당신은 내가 입력을 볼 수 없습니다