閲覧ありがとうございます。
今とあるボードゲームを作っているのですが、
盤面にある駒の集計方法が複雑で行き詰りました。
O|O| | | |O|O|O|
| | | | |O| |O|
O| | | | | | | |
このように不規則に盤面上に置かれた駒の内、
縦横2つ以上でつながった塊を検出しないといけません。
上記の場合、2と5になります。
盤面は9*9で、現在はint型の一次元配列で表しています。
for文で横を検出して縦に・・・などいろいろ試しましたが、
全てうまく作れませんでした。
自分で組みますので、どなたかアイデアいただけないでしょうか。
他の関数は調節できますので、盤面に関してはint型の一次元配列から
変更有りでも問題ありません
盤面の探索で
Re: 盤面の探索で
これって、探索結果をどういう風に受け取りたいのでしょうか？
例えばこの問題を解くsearch(...)という関数があったとして、利用する側はどういうコードになりますか？
例えばこの問題を解くsearch(...)という関数があったとして、利用する側はどういうコードになりますか？
-
hana
Re: 盤面の探索で
存在する塊1つ1つに対して、その塊を構成するOの数を受け取りたいと思っています。
int block[128]を関数の引数にして
先の例を引用すると
block[0] = 2
block[1] = 5
のような形が理想です。
int block[128]を関数の引数にして
先の例を引用すると
block[0] = 2
block[1] = 5
のような形が理想です。
Re: 盤面の探索で
void search(int x, int y, int *cnt)
{
int c = Board[x][y];
Board[x][y]=0;
(*cnt)++;
if(x+1<9 && Board[x+1][y]==c) search(x+1, y, cnt);
if(y+1<9 && Board[x][y+1]==c) search(x, y+1, cnt);
if(x-1>=0 && Board[x-1][y]==c) search(x-1, y, cnt);
if(y-1>=0 && Board[x][y-1]==c) search(x, y-1, cnt);
Board[x][y]=c;
}
再帰関数を使ってこんな感じでできるかと。
一次元配列にしたいなら少し書き直さないといけませんが。
塊ごとにカウントしたいなら、チェック済みか印をつける必要があるかな。
全然検証してませんが、とりあえずアイデアということで。
Re: 盤面の探索で
こんな感じでしょうか。
もっといい方法があると思いますが。
もっといい方法があると思いますが。
#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;
}
-
ヒムカイヒナタ
Re: 盤面の探索で
hssさんがおっしゃっておられた再帰関数でちょっと書いてみました。
ぽこさんのボードデータを拝借しましたので結果はぽこさんのものと同一になるはずです。
再帰関数は、自分で自分をよび出す処理の事です。（今回の場合、searchの中でsearchを呼んでいる）
再帰関数は、今回のような処理を綺麗且つコンパクトに書くことが可能ですが、
再帰呼び出ししたその分メモリ食っていきますし、
処理速度的に見てもあまり効率的ではないです。
大量に再帰呼び出しが発生する場合はぽこさんが書かれたコードのような
非再帰関数等を検討した方がいいかと思われますので可能なら両方の方法を
理解して場に応じたコードが書ければ、それがベストかと思います。
長々と失礼しました。
ぽこさんのボードデータを拝借しましたので結果はぽこさんのものと同一になるはずです。
/**
@file main.cpp
@brief ブロックの塊を見つける
*/
//---- Include File -----------------------------------------------------------
#include <stdio.h>
//---- Constant Declaration ---------------------------------------------------
//---- Macro Declaration ------------------------------------------------------
#define BOARD_WIDTH 9 // ボード横幅
#define BOARD_HEIGHT 9 // ボード縦幅
#define CHECKED 1 // チェック済
#define THRESHOLD 2 // 塊の最小構成
//---- Data Type Declaration --------------------------------------------------
//---- Prototype Declaration --------------------------------------------------
//---- Global Variable Declaration --------------------------------------------
int g_aBoard[ BOARD_WIDTH ][ BOARD_HEIGHT ] = { // ボード上の状態
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 g_aCheckBoard[ BOARD_WIDTH ][ BOARD_HEIGHT ]; // 確認用のボード
//---- Function Declaration ---------------------------------------------------
/**
@brief 検索するのに有効なマス目か？
@retval true 有効
@retval false 無効
*/
bool isEnable( int i_x, int i_y )
{
// ボード上且つ、まだ調べていないマスか？
return ( i_x < 0 || i_x >= BOARD_WIDTH ||
i_y < 0 || i_y >= BOARD_HEIGHT ||
!g_aCheckBoard[ i_x ][ i_y ] );
}
//-----------------------------------------------------------------------------
/**
@brief 検索
@param [in] i_x X座標
@param [in] i_y Y座標
@param [in/out] io_pCnt カウンターのポインタ
*/
void search( int i_x, int i_y, int* io_pCnt )
{
// 今から調べるので確認用ボードにチェックをつける
g_aCheckBoard[ i_x ][ i_y ] = CHECKED;
// マスチェック
if( g_aBoard[ i_x ][ i_y ] ){
// 駒があったから増やす
++( *io_pCnt );
// 次のマスの検索へ
if( isEnable( i_x, i_y-1 ) ){ // 上
search( i_x, i_y-1, io_pCnt );
}
if( isEnable( i_x, i_y+1 ) ){ // 下
search( i_x, i_y+1, io_pCnt );
}
if( isEnable( i_x-1, i_y ) ){ // 左
search( i_x-1, i_y, io_pCnt );
}
if( isEnable( i_x+1, i_y ) ){ // 右
search( i_x+1, i_y, io_pCnt );
}
}
}
//-----------------------------------------------------------------------------
/**
@brief メイン関数
*/
int main()
{
int aNum[ 32 ]; // ブロック構成数格納先。３２個もありゃ足りるだろ……
// ブロック構成数格納先の初期化
for( int i = 0; i < 32; ++i ){
aNum[ i ] = 0;
}
// チェック用ボードの初期化
for( int i = 0; i < BOARD_WIDTH; ++i ){
for( int j = 0; j < BOARD_HEIGHT; ++j ){
g_aCheckBoard[ i ][ j ] = 0;
}
}
// 検索
int index = 0;
for( int i = 0; i < BOARD_WIDTH; ++i ){
for( int j = 0; j < BOARD_HEIGHT; ++j ){
int counter = 0; // カウント用変数
search( i, j, &counter );
// ２個以上で塊が構成されていたらデータを格納してインデックスを増加
if( THRESHOLD <= counter ){
aNum[ index++ ] = counter;
}
}
}
printf( "塊の数：%d個\n\n", index );
for( int i = 0; i < index; ++i ){
printf( "塊%02dの構成数：%d個\n", i, aNum[ i ] );
}
return 0;
}
再帰関数は、今回のような処理を綺麗且つコンパクトに書くことが可能ですが、
再帰呼び出ししたその分メモリ食っていきますし、
処理速度的に見てもあまり効率的ではないです。
大量に再帰呼び出しが発生する場合はぽこさんが書かれたコードのような
非再帰関数等を検討した方がいいかと思われますので可能なら両方の方法を
理解して場に応じたコードが書ければ、それがベストかと思います。
長々と失礼しました。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター