解答例を。
自力で考えようとかプログラミングに興味がない人はみない方向で。
さて、とりあえず、色々面倒なので、選択したチップを抜き書きした配列を用意し、そのデータを利用して妥当性をチェックしてみるルーチン。
インデントが効かないので、"→"を4タブまたは半角スペース4文字分に置換してくだしあ。
コメント以外に解説は付けません。しかし、この手法そのものは、様々な判定をする上では汎用性が高いアルゴリズムの組み方なので、理解すると色々便利かも知れない。
=================================================================
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
// Neighbor型共用体
// Top,Right,Down,Leftの要素名とインデックス番号を対応させるため。
typedef union _Neighbor
{
→char f[4];
→struct { char Top, Right, Down, Left; };
} Neighbor;
// 方向指定番号
typedef enum _Direction {
→UP = 0, RIGHT, DOWN, LEFT,
} Direction;
// 面状態を格納する構造体
typedef struct _FaceState {
→char Face;→→// 現在取り扱っている面番号
→char Top;→→// cube_neighbor_setの何番目(0～3)の面が、実際の上側となるか？
} FaceState;
// 立方体の各面について、その面と隣接する面の番号を（仮想的な上側から順に）時計回りに与える。
// 配列は、面番号順に格納されている。
const Neighbor cube_neighbor_set[] = {
→{ 1, 2, 3, 4, },
→{ 5, 2, 0, 4, },
→{ 5, 3, 0, 1, },
→{ 5, 4, 0, 2, },
→{ 5, 1, 0, 3, },
→{ 1, 4, 3, 2, },
};
// 立方体の面について、どの面とどの面が向かい合わせになるかを与える。
// face_pair[i]=jの時、面iと面jが向かい合わせとなる。
//
const int face_pair[] = {5, 3, 4};
// 立方体の面数
#define FACE_COUNT→6
// 向かい合わせの面の合計値
#define SUM_OF_PAIR→7
// 問い合わせデータ幅
#define WIDTH→8
// 問い合わせデータ高さ
#define HEIGHT→8
// Free関数のwrapper
#define SAFEFREE(a)→{free(a);a=NULL;}
// qsortのコールバック関数
// int compare_char(const void *a, counst void *b)
// 引数：→const void *a→第１引数比較値へのポインタ
//→→→const void *b→第２引数比較値へのポインタ
// 返値：→int→→第１引数＞第二引数ならば正の値
//→→→→→第１引数＝第二引数ならば0
//→→→→→第１引数＞第二引数ならば負の値
//→→→→→をそれぞれ返す。(qsort関数の要求仕様に準拠)
int compare_char(const void *a, const void *b)
{
→char *_a = (char *)a;
→char *_b = (char *)b;
return *_a – *_b;
}
// CCubeクラス
// 立方体の面情報を処理するクラス
class CCube
{
private:
→// 立方体の面情報を格納する配列。６面それぞれに張り付けられた値を保持する。
→char plain[FACE_COUNT];
→// 面状態の保持構造体
→FaceState fs;
public:
→// Constructor
→CCube()
→{
→→Reset();
→}
→// CCube::Reset()
→// 引数：なし
→// 返値：なし
→// 機能：立方体が持つ面情報をクリアする。
→void Reset()
→{
→→memset(this->plain, 0, sizeof(plain));
→→memset(&fs, 0, sizeof(fs));
→}
→// CCube::ScanFace( int Face, int SearchFace)
→// 引数：→int Face→→検索対象となる面番号
→//→→→int SearchFace→検索する面番号
→// 返値：int インデクス番号
→// 機能：ある面から別の面への遷移する際、移動元の面が異動先の面のcube_neighbor_set上で
→//→→→何番目のインデクスに当たるかを検索し、その値を返す。
→int ScanFace( int Face, int SearchFace )
→{
→→int i = 0;
→→const char *p = &cube_neighbor_set[Face].f[0];
→→for( ; i < 4; ++i )
→→{
→→→if( *p++ == SearchFace )
→→→{
→→→→return i;
→→→}
→→}
→→return -1;
→}
→// FaceState CCube::MoveFace( int MoveTo )
→// 引数：→int MoveTo→移動先の面を、現在の面から見て上下左右の方向で指定する
→// 返値：→FaceState→クラスのfsメンバを返す
→// 機能：→このキューブインスタンスの面状態を更新し
→//→→→現在位置から、指定された方向へ移動する。
→FaceState MoveFace( int MoveTo )
→{
→→// 次の面にとって、どちらから来たことになるか
→→int FromDirection = MoveTo ^ 2;
→→// 次の面のインデックス番号を取得
→→int NextFace = cube_neighbor_set[ fs.Face ].f[ (fs.Top + MoveTo) & 3 ];
→→// その面にとって、どちらの面から来たか
→→int FromIndex = ScanFace( NextFace, fs.Face );
→→// 面状態を更新する。
→→fs.Top = (FromIndex – FromDirection) & 3;
→→fs.Face = NextFace;
→→return fs;
→}
→// void CCube::RegFace( char *, int, int);
→// access:public
→// 引数：→char *field→→問い合わせデータ配列へのポインタ
→//→→→int x,y→→→問い合わせデータ上の貼付元位置
→// 返値：→void
→// 機能：→問い合わせデータ上の指定位置の値を立方体上に格納する
→void RegFace( char *field, int x, int y )
→{
→→char *pos = field + y * WIDTH + x;
→→// 現在位置にダイス面が存在しなければ処理を中断
→→if( !*pos )
→→{
→→→return;
→→}
→→// 面をキューブに貼り付け
→→plain[this->fs.Face] = *pos;
→→// 現在位置のダイス面を消す
→→*pos = 0;
→→// 上下左右の隣接位置に対して再スキャン
→→FaceState fs;
→→if( y > 0 )→→→→→→→// 問い合わせデータ上で、まだ上側が残っていれば処理する
→→{→
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( UP );→→→→→// 上へ移動
→→→RegFace( field, x, y – 1 );→→// 上面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( x > 0 )→→→→→→→// 問い合わせデータ上で、まだ左側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( LEFT );→→→→// 左へ移動
→→→RegFace( field, x – 1, y );→→// 左面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( x < WIDTH – 1 )→→→→→// 問い合わせデータ上で、まだ右側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( RIGHT );→→→→// 右へ移動
→→→RegFace( field, x + 1, y );→→// 右面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( y < HEIGHT – 1 )→→→→// 問い合わせデータ上で、まだ下側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( DOWN );→→→→// 下へ移動
→→→RegFace( field, x, y + 1 );→→// 下面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→}
→// bool IsDice()
→// 引数：なし
→// 返値：bool→→true:→サイコロである
→//→→→→→false:→サイコロではない
→bool IsDice()
→{
→→// ダイス判定条件
→→// 1.全ての面が完備
→→int i;
→→for(i = 0; i < FACE_COUNT; ++i)
→→{
→→→if(!plain[i])
→→→{
→→→→return false;
→→→}
→→}
→→// 2.3組の対面の和が7
→→for(i = 0; i < FACE_COUNT >> 1; ++i)
→→{
→→→if( SUM_OF_PAIR != plain[i] + plain[face_pair[i]])
→→→{
→→→→return false;
→→→}
→→}
→→// 3.1～6の全ての値が使用されている
→→qsort( plain, FACE_COUNT, sizeof(char), compare_char );
→→for(i = 0; i < FACE_COUNT; ++i)
→→{
→→→if(plain[i] != i + 1)
→→→{
→→→→return false;
→→→}
→→}
→→return true;
→}
→~CCube(){}
};
bool IsCube(char *field)
{
→CCube cube;
→// 開始位置を探す
→int x, y, i;
→// 開始行(y)を探す
→__int64 *p = (__int64 *)field;
→for( i = 0; i < HEIGHT; ++i, ++p )
→{
→→if( *p )
→→{
→→→y = i;
→→→break;
→→}
→}
→if( HEIGHT == i )
→{
→→return false;→→→→→// 問い合わせデータが空だった
→}
→char *q = (char *)&p[y];
→// 開始列(x)を探す
→for( i = 0; i < WIDTH; ++i, ++q )
→{
→→if( *q )
→→{
→→→x = i;
→→→break;
→→}
→}
→// 開始位置が特定できたので、再帰的にキューブ面に数値を貼り付けていく
→cube.RegFace( field, x, y );
→// 張り付けてできた立方体はサイコロになっているか？
→return cube.IsDice();
}
typedef struct _Rect
{
→int x;
→int y;
} Rect;
// 問題データ
// 1～6の目の位置を順にx,y座標で記述。
Rect question[] =
{
→{ 1, 1, },
→{ 0, 1, },
→{ 2, 0, },
→{ 2, 2, },
→{ 3, 1, }, // 下の行と入れ替えるとサイコロが完成する
→{ 2, 1, }, //
};
// 問題データの貼付
void setAnswer(char *field)
{
→for(int i = 0; i < FACE_COUNT; ++i)
→{
→→field[question[i].y * WIDTH + question[i].x] = i + 1;
→}
}
int main(int argc, char* argv[])
{
→char *field_table = (char *)calloc(WIDTH, HEIGHT);
→// 問題作成
→setAnswer(field_table);
→// サイコロチェック呼び出し
→if( IsCube(field_table) )
→{
→→printf("Cube!¥n");
→}
→else
→{
→→printf("Not Cube!¥n");
→}
→SAFEFREE(field_table);
→return 0;
}
自力で考えようとかプログラミングに興味がない人はみない方向で。
さて、とりあえず、色々面倒なので、選択したチップを抜き書きした配列を用意し、そのデータを利用して妥当性をチェックしてみるルーチン。
インデントが効かないので、"→"を4タブまたは半角スペース4文字分に置換してくだしあ。
コメント以外に解説は付けません。しかし、この手法そのものは、様々な判定をする上では汎用性が高いアルゴリズムの組み方なので、理解すると色々便利かも知れない。
=================================================================
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
// Neighbor型共用体
// Top,Right,Down,Leftの要素名とインデックス番号を対応させるため。
typedef union _Neighbor
{
→char f[4];
→struct { char Top, Right, Down, Left; };
} Neighbor;
// 方向指定番号
typedef enum _Direction {
→UP = 0, RIGHT, DOWN, LEFT,
} Direction;
// 面状態を格納する構造体
typedef struct _FaceState {
→char Face;→→// 現在取り扱っている面番号
→char Top;→→// cube_neighbor_setの何番目(0～3)の面が、実際の上側となるか？
} FaceState;
// 立方体の各面について、その面と隣接する面の番号を（仮想的な上側から順に）時計回りに与える。
// 配列は、面番号順に格納されている。
const Neighbor cube_neighbor_set[] = {
→{ 1, 2, 3, 4, },
→{ 5, 2, 0, 4, },
→{ 5, 3, 0, 1, },
→{ 5, 4, 0, 2, },
→{ 5, 1, 0, 3, },
→{ 1, 4, 3, 2, },
};
// 立方体の面について、どの面とどの面が向かい合わせになるかを与える。
// face_pair[i]=jの時、面iと面jが向かい合わせとなる。
//
const int face_pair[] = {5, 3, 4};
// 立方体の面数
#define FACE_COUNT→6
// 向かい合わせの面の合計値
#define SUM_OF_PAIR→7
// 問い合わせデータ幅
#define WIDTH→8
// 問い合わせデータ高さ
#define HEIGHT→8
// Free関数のwrapper
#define SAFEFREE(a)→{free(a);a=NULL;}
// qsortのコールバック関数
// int compare_char(const void *a, counst void *b)
// 引数：→const void *a→第１引数比較値へのポインタ
//→→→const void *b→第２引数比較値へのポインタ
// 返値：→int→→第１引数＞第二引数ならば正の値
//→→→→→第１引数＝第二引数ならば0
//→→→→→第１引数＞第二引数ならば負の値
//→→→→→をそれぞれ返す。(qsort関数の要求仕様に準拠)
int compare_char(const void *a, const void *b)
{
→char *_a = (char *)a;
→char *_b = (char *)b;
return *_a – *_b;
}
// CCubeクラス
// 立方体の面情報を処理するクラス
class CCube
{
private:
→// 立方体の面情報を格納する配列。６面それぞれに張り付けられた値を保持する。
→char plain[FACE_COUNT];
→// 面状態の保持構造体
→FaceState fs;
public:
→// Constructor
→CCube()
→{
→→Reset();
→}
→// CCube::Reset()
→// 引数：なし
→// 返値：なし
→// 機能：立方体が持つ面情報をクリアする。
→void Reset()
→{
→→memset(this->plain, 0, sizeof(plain));
→→memset(&fs, 0, sizeof(fs));
→}
→// CCube::ScanFace( int Face, int SearchFace)
→// 引数：→int Face→→検索対象となる面番号
→//→→→int SearchFace→検索する面番号
→// 返値：int インデクス番号
→// 機能：ある面から別の面への遷移する際、移動元の面が異動先の面のcube_neighbor_set上で
→//→→→何番目のインデクスに当たるかを検索し、その値を返す。
→int ScanFace( int Face, int SearchFace )
→{
→→int i = 0;
→→const char *p = &cube_neighbor_set[Face].f[0];
→→for( ; i < 4; ++i )
→→{
→→→if( *p++ == SearchFace )
→→→{
→→→→return i;
→→→}
→→}
→→return -1;
→}
→// FaceState CCube::MoveFace( int MoveTo )
→// 引数：→int MoveTo→移動先の面を、現在の面から見て上下左右の方向で指定する
→// 返値：→FaceState→クラスのfsメンバを返す
→// 機能：→このキューブインスタンスの面状態を更新し
→//→→→現在位置から、指定された方向へ移動する。
→FaceState MoveFace( int MoveTo )
→{
→→// 次の面にとって、どちらから来たことになるか
→→int FromDirection = MoveTo ^ 2;
→→// 次の面のインデックス番号を取得
→→int NextFace = cube_neighbor_set[ fs.Face ].f[ (fs.Top + MoveTo) & 3 ];
→→// その面にとって、どちらの面から来たか
→→int FromIndex = ScanFace( NextFace, fs.Face );
→→// 面状態を更新する。
→→fs.Top = (FromIndex – FromDirection) & 3;
→→fs.Face = NextFace;
→→return fs;
→}
→// void CCube::RegFace( char *, int, int);
→// access:public
→// 引数：→char *field→→問い合わせデータ配列へのポインタ
→//→→→int x,y→→→問い合わせデータ上の貼付元位置
→// 返値：→void
→// 機能：→問い合わせデータ上の指定位置の値を立方体上に格納する
→void RegFace( char *field, int x, int y )
→{
→→char *pos = field + y * WIDTH + x;
→→// 現在位置にダイス面が存在しなければ処理を中断
→→if( !*pos )
→→{
→→→return;
→→}
→→// 面をキューブに貼り付け
→→plain[this->fs.Face] = *pos;
→→// 現在位置のダイス面を消す
→→*pos = 0;
→→// 上下左右の隣接位置に対して再スキャン
→→FaceState fs;
→→if( y > 0 )→→→→→→→// 問い合わせデータ上で、まだ上側が残っていれば処理する
→→{→
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( UP );→→→→→// 上へ移動
→→→RegFace( field, x, y – 1 );→→// 上面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( x > 0 )→→→→→→→// 問い合わせデータ上で、まだ左側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( LEFT );→→→→// 左へ移動
→→→RegFace( field, x – 1, y );→→// 左面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( x < WIDTH – 1 )→→→→→// 問い合わせデータ上で、まだ右側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( RIGHT );→→→→// 右へ移動
→→→RegFace( field, x + 1, y );→→// 右面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→→if( y < HEIGHT – 1 )→→→→// 問い合わせデータ上で、まだ下側が残っていれば処理する
→→{
→→→fs = this->fs;→→→→→// 現在の状態を待避
→→→MoveFace( DOWN );→→→→// 下へ移動
→→→RegFace( field, x, y + 1 );→→// 下面を登録する
→→→this->fs = fs;→→→→→// 状態を元に戻す
→→}
→}
→// bool IsDice()
→// 引数：なし
→// 返値：bool→→true:→サイコロである
→//→→→→→false:→サイコロではない
→bool IsDice()
→{
→→// ダイス判定条件
→→// 1.全ての面が完備
→→int i;
→→for(i = 0; i < FACE_COUNT; ++i)
→→{
→→→if(!plain[i])
→→→{
→→→→return false;
→→→}
→→}
→→// 2.3組の対面の和が7
→→for(i = 0; i < FACE_COUNT >> 1; ++i)
→→{
→→→if( SUM_OF_PAIR != plain[i] + plain[face_pair[i]])
→→→{
→→→→return false;
→→→}
→→}
→→// 3.1～6の全ての値が使用されている
→→qsort( plain, FACE_COUNT, sizeof(char), compare_char );
→→for(i = 0; i < FACE_COUNT; ++i)
→→{
→→→if(plain[i] != i + 1)
→→→{
→→→→return false;
→→→}
→→}
→→return true;
→}
→~CCube(){}
};
bool IsCube(char *field)
{
→CCube cube;
→// 開始位置を探す
→int x, y, i;
→// 開始行(y)を探す
→__int64 *p = (__int64 *)field;
→for( i = 0; i < HEIGHT; ++i, ++p )
→{
→→if( *p )
→→{
→→→y = i;
→→→break;
→→}
→}
→if( HEIGHT == i )
→{
→→return false;→→→→→// 問い合わせデータが空だった
→}
→char *q = (char *)&p[y];
→// 開始列(x)を探す
→for( i = 0; i < WIDTH; ++i, ++q )
→{
→→if( *q )
→→{
→→→x = i;
→→→break;
→→}
→}
→// 開始位置が特定できたので、再帰的にキューブ面に数値を貼り付けていく
→cube.RegFace( field, x, y );
→// 張り付けてできた立方体はサイコロになっているか？
→return cube.IsDice();
}
typedef struct _Rect
{
→int x;
→int y;
} Rect;
// 問題データ
// 1～6の目の位置を順にx,y座標で記述。
Rect question[] =
{
→{ 1, 1, },
→{ 0, 1, },
→{ 2, 0, },
→{ 2, 2, },
→{ 3, 1, }, // 下の行と入れ替えるとサイコロが完成する
→{ 2, 1, }, //
};
// 問題データの貼付
void setAnswer(char *field)
{
→for(int i = 0; i < FACE_COUNT; ++i)
→{
→→field[question[i].y * WIDTH + question[i].x] = i + 1;
→}
}
int main(int argc, char* argv[])
{
→char *field_table = (char *)calloc(WIDTH, HEIGHT);
→// 問題作成
→setAnswer(field_table);
→// サイコロチェック呼び出し
→if( IsCube(field_table) )
→{
→→printf("Cube!¥n");
→}
→else
→{
→→printf("Not Cube!¥n");
→}
→SAFEFREE(field_table);
→return 0;
}
2009年10月21日
beautyplanets
