매트릭스 C++에서 영역 찾기

Question

매트릭스에 몇 개의 영역과 몇 개의 요소가 있는지 찾아야합니다. 행렬은 0과 1로 채워집니다. 인접한 1 (대각선, 수직 또는 수평) 인 경우 영역이 있습니다.

int count_regions(int *arr, int rows, int cols) { 
    int region_count = 0; 

    for (int first_index = 0; first_index != rows * cols; ++ first_index) { 
     if (arr[ first_index ] == 0) continue; 

     ++ region_count; 

     int first_row = first_index/cols, first_col = first_index % cols; 
     int last_col; 
     for (last_col = first_col; 
       last_col != cols && arr[ first_row * cols + last_col ] != 0; 
       ++ last_col) ; 

     for (int last_row = first_row; 
       last_row != rows && arr[ last_row * cols + first_col ] != 0; 
       ++ last_row) { 
      for (int col = first_col; col != last_col; ++ col) { 
       arr[ last_row * cols + col ] = 0; 
      } 
     } 
    } 
    return region_count; 
} 

Answer 1

알고리즘은 connected components labelling입니다.