コード:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define BOARD_X 9
#define BOARD_Y 9
#define NO_GROUP 0
/* 0がコマなし、1がコマあり*/
int board[BOARD_X * BOARD_Y] = {
1,1,0,0,0,1,1,1,0,
0,0,0,0,0,1,0,1,0,
0,0,0,0,0,0,0,0,0,
1,0,1,0,1,0,1,0,0,
0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,1,1,0,
0,1,0,0,0,1,0,1,0,
0,1,1,1,1,1,0,0,0,
};
int group_no = NO_GROUP;
int block[BOARD_X * BOARD_Y] = { 0 };
/*
ボード上の(x,y)にコマが存在するかを確認
0:なし
1:あり
*/
int has_piece( int x, int y, int max_x, int max_y )
{
if ( x < 0 || max_x <= x || y < 0 || max_y <= y ) {
return 0;
}
return board[BOARD_X * y + x];
}
/* ボード上の(x,y)に割り振ったグループ番号を取得 */
int get_group_no( int x, int y, int max_x, int max_y )
{
if ( x < 0 || max_x <= x || y < 0 || max_y <= y ) {
return NO_GROUP;
}
return block[BOARD_X * y + x];
}
void merge_group( int g1, int g2, int * block, int size )
{
int less_no = g1 < g2 ? g1 : g2;
int gt_no = g1 < g2 ? g2 : g1;
int adjust = gt_no - less_no;
int i;
assert( adjust > 0 );
for ( i = 0; i < size; i++ ) {
block[i] = block[i] < gt_no ? block[i] : block[i] - adjust;
}
}
int cmp_cluster( const void * s1, const void * s2 )
{
return *(int *)s2 - *(int *)s1;
}
/*
配列blockに塊の大きさを塊が大きい順に格納。
戻り値は塊の数。
*/
int search( int board[], int x, int y, int block[] )
{
int group_no = 0;
int i;
int j;
memset( block, NO_GROUP , x * y * sizeof(int) );
/* 順繰り見ていく */
for ( i = 0; i < y; i++ ) {
for ( j = 0; j < x; j++ ) {
int above_group;
int left_group;
if ( !board[i * BOARD_X + j] ) {
/* コマがないからどのグループにも所属せず */
block[BOARD_X * i + j] = NO_GROUP;
continue;
}
/* ここに来るってことはコマが存在する。 */
/* 隣接したセルにコマがあるか確認 */
if ( !(has_piece( j, i - 1, x, y ) || has_piece( j + 1, i, x, y ) || has_piece( j, i + 1, x, y ) || has_piece( j - 1, i, x, y ) ) ) {
/* 隣接セルのどこにもコマがない場合、ぼっち確定 */
block[BOARD_X * i + j] = NO_GROUP;
continue;
}
/* ここに来るってことは、どこかのグループに所属することになる */
/* すでに検索済みのセルのグループ番号を取得 */
above_group = get_group_no( j, i - 1, x, y );
left_group = get_group_no( j - 1, i, x, y );
if ( above_group ) {
/* 上と同じグループに入る */
block[BOARD_X * i + j] = above_group;
if ( left_group ) {
/* 両方にグループが存在する場合は合併。グループ番号が小さい方に合わせる) */
if ( above_group != left_group ) {
merge_group( above_group, left_group, block , x * y );
group_no--;
}
}
} else if ( left_group ) {
/* 上にコマがなく左にコマがある場合は左のグループに入る */
block[BOARD_X * i + j] = left_group;
} else {
/* 隣接セルのどこにもコマがない場合、新グループ立ち上げ */
block[BOARD_X * i + j] = ++group_no;
}
}
}
/* 塊が大きな順に並べ替える */
qsort( block, x * y, sizeof(int), cmp_cluster );
/* 最後にグループごとの個数を数える */
for ( i = 0, j = 0; i < group_no; i++ ) {
int c = 0;
int k;
for ( k = j; k < x * y; k++ ) {
if ( block[j] != block[k] ) {
break;
}
c++;
}
j = k;
block[i] = c;
}
return group_no;
}
int main()
{
int i;
int count = search( board, BOARD_X, BOARD_Y, block );
assert( count == 3 );
for ( i = 0; i < count; i++ ) {
printf( "block[%d]=%d\n", i, block[i] );
}
return 0;
}