- 絶対に宝が無いとわかるところを選ばない
- ヒントの数値がでかいやつの周囲を先に選ぶ
みたいな簡素な方法を実装してみました.
(微妙にところどころC++成分入ってますが,読める範疇かと.)
全体的に使う構造体と定数
//[Pos.h]
#pragma once
//座標(x,y)を表すだけの構造体
struct Pos
{
int x, y;
Pos( int x=0,int y=0 ) : x(x),y(y) {}
};
//[SysDefs.h]
#pragma once
//マップのサイズ
#define MAP_W 10
#define MAP_H 10
//宝の総数
#define N_TREASURE 8
ゲームのルール部分側の実装("Sys"とかいう命名がダサい^^)
//[SysSide.h]
//ゲームのルール側の実装
#pragma once
#include "Pos.h"
//状態初期化.
void Sys_Init();
//指定のマスを開く.
//・Sys_Show()によって表示される内容が更新される.
//・指定マスに関する情報を返す.
//
//戻り値は,
//・指定マスに宝が無い場合は,その8近傍に存在する宝の個数
//・指定マスが宝の場合には,負の値
int Sys_Open( const Pos &OpenPos );
//現状態の表示
void Sys_Show();
//[SysSide.cpp]
#include "stdafx.h" //VC
#include "SysSide.h"
#include "SysDefs.h"
#include <cmath>
//表示内容バッファ
static char ShowBuff[MAP_H][MAP_W + 1];
//※とりあえず宝の位置は固定のハードコーディング※
static const Pos TreasurePos[N_TREASURE] =
{
Pos( 0,1 ), Pos( 1,8 ), Pos( 2,2 ), Pos( 5,0 ),
Pos( 5,4 ), Pos( 6,4 ), Pos( 6,3 ), Pos( 8,7 )
};
//
void Sys_Init()
{
//全マスの表示内容を'+'に初期化
for( int y=0; y<MAP_H; ++y )
{
for( int x=0; x<MAP_W; ++x ){ ShowBuff[y][x] = '+'; }
ShowBuff[y][MAP_W] = '\0';
}
//※本来はここで,TreasurePos[]の内容を乱数とか使って決めれば良いかと※
}
//
int Sys_Open( const Pos &OpenPos )
{
int nTreasureArround = 0;
for( int i=0; i<N_TREASURE; ++i )
{
int dx = abs( OpenPos.x - TreasurePos[i].x );
int dy = abs( OpenPos.y - TreasurePos[i].y );
if( dx==0 && dy==0 )
{
ShowBuff[OpenPos.y][OpenPos.x] = '$';
return -1;
}
if( dx<=1 && dy<=1 ){ ++nTreasureArround; }
}
ShowBuff[OpenPos.y][OpenPos.x] = '0' + nTreasureArround;
return nTreasureArround;
}
//
void Sys_Show()
{
for( int y=0; y<MAP_H; ++y ){ printf( "%s\n", ShowBuff[y] ); }
}
アルゴリズム側のヘッダ
//[AlgoSide.h]
//宝を探すアルゴリズム側の実装
#pragma once
#include "Pos.h"
//状態初期化
void Algo_Init();
//開くマスを決める.
Pos Algo_DecideOpenPos();
//アルゴリズムに,マスPに関する情報を与える.
//( Algo_DecideOpenPos()が返した場所Pに関する,Sys_Open(P)の結果をアルゴリズムに教える用 )
//
//InfoVal は
//・マスPに宝が無い場合は,その8近傍に存在する宝の個数
//・マスPが宝の場合には,負の値
void Algo_Update( const Pos &P, int InfoVal );
mainはこんな感じで.
#include "SysSide.h"
#include "SysDefs.h"
#include "AlgoSide.h"
int _tmain(int argc, _TCHAR* argv[])
{
//初期化
Sys_Init();
Algo_Init();
//宝探す処理
int nIter = 0;
int nTreasureRest = N_TREASURE; //未発見の宝の個数
while( nTreasureRest>0 && nIter<MAP_W*MAP_H )
{
++nIter;
Pos OpenPos = Algo_DecideOpenPos();
int OpenResult = Sys_Open( OpenPos );
if( OpenResult < 0 ){ --nTreasureRest; }
Algo_Update( OpenPos, OpenResult );
printf( "Turn %d : (%d,%d) -> %c\n", nIter, OpenPos.x, OpenPos.y, (OpenResult<0 ? '$' : '0'+OpenResult) );
Sys_Show();
printf( "-------------------------------\n\n" );
}
printf( "Total Turn = %d\n", nIter );
printf( "Rest Treasure Count = %d\n", nTreasureRest );
getchar(); //Press Enter_Key to Quit
return 0;
}
(…と,ここまでくらいの物を質問する側で指定してもらえると,回答書く人もそれを読む人もやり易くてよいのではないなかぁ,とか思う)
で,アルゴリズムの実装.
//[AlgoSide.cpp]
#include "stdafx.h" //VC
#include "AlgoSide.h"
#include "SysDefs.h"
//作業関数.
//Pの8近傍のマスの座標をDstの先頭側に入れる.
//戻り値は入れた個数(=近傍マスの個数)
int GetNeighbors( const Pos &P, Pos (&Dst)[8] )
{
const int DX[8] = { -1, 0, 1, -1,1, -1,0,1 };
const int DY[8] = { -1,-1,-1, 0,0, 1,1,1 };
int nNeighbor = 0;
for( int i=0; i<8; ++i )
{
int x = P.x + DX[i];
int y = P.y + DY[i];
if( x<0 || y<0 || x>=MAP_W || y>=MAP_H )continue;
Dst[ nNeighbor ] = Pos(x,y);
++nNeighbor;
}
return nNeighbor;
}
//マスの情報用構造体
struct Info
{
bool IsOpened; //開いたマスはtrueにする
bool TreasureNotExist; //宝が無いとわかった場所はtrueにする→次回から見なくていい
int InfoVal; //マスを開いて得られた結果.
int NotOpenedPosArround; //8近傍で開いていないマスの個数
int nFoundTreasureArround; //8近傍に見つけた宝の個数
Info() :
IsOpened(false), TreasureNotExist(false),
InfoVal( -1 ), NotOpenedPosArround(8), nFoundTreasureArround(0)
{}
};
//情報バッファ
static Info Data[MAP_H][MAP_W];
//(x,y)のスコアを計算する作業関数
double CalcScore( int x, int y )
{
if( Data[y][x].IsOpened || Data[y][x].TreasureNotExist )return -1;
double Score = 0;
Pos NeighborPos[8];
int n = GetNeighbors( Pos(x,y), NeighborPos );
for( int i=0; i<n; ++i )
{
const auto &ND = Data[ NeighborPos[i].y ][ NeighborPos[i].x ];
if( ND.IsOpened )
{
if( ND.InfoVal < 0 )continue; //宝のマスからは情報を得られない
if( ND.InfoVal <= ND.nFoundTreasureArround )
{//このマスに宝はない
Data[y][x].TreasureNotExist = true; //次回以降見なくていいフラグを立てておく
return -1;
}
Score += (double)ND.InfoVal / ND.NotOpenedPosArround;
}
}
return Score;
}
//初期化
void Algo_Init()
{
for( int x=1; x<=MAP_W-2; ++x )
{ Data[0][x].NotOpenedPosArround = Data[MAP_H-1][x].NotOpenedPosArround = 5; }
for( int y=1; y<=MAP_H-2; ++y )
{ Data[y][0].NotOpenedPosArround = Data[y][MAP_W-1].NotOpenedPosArround = 5; }
Data[0][0].NotOpenedPosArround = 3;
Data[MAP_H-1][0].NotOpenedPosArround = 3;
Data[0][MAP_W-1].NotOpenedPosArround = 3;
Data[MAP_H-1][MAP_W-1].NotOpenedPosArround = 3;
}
//開く箇所を決める
Pos Algo_DecideOpenPos( )
{ //全てのマスに関して,適当なルールで得点を算出し,一番得点が高い個所を開く場所とする
Pos Ret;
double MaxScore = -1;
for( int y=0; y<MAP_H; ++y )
{
for( int x=0; x<MAP_W; ++x )
{
double Score = CalcScore( x,y );
if( MaxScore < Score )
{
Ret = Pos( x,y );
MaxScore = Score;
}
}
}
return Ret;
}
//情報更新
void Algo_Update( const Pos &P, int InfoVal )
{
if( Data[P.y][P.x].IsOpened )return; //一応チェック
//マスPの情報更新
Data[P.y][P.x].IsOpened = true;
Data[P.y][P.x].InfoVal = InfoVal;
{//Pの周囲のマスの情報を更新
Pos NeighborPos[8];
int n = GetNeighbors( P, NeighborPos );
for( int i=0; i<n; ++i )
{
--Data[ NeighborPos[i].y ][ NeighborPos[i].x ].NotOpenedPosArround;
if( InfoVal<0 ) //マスPに宝が見つかったとき
{ ++Data[ NeighborPos[i].y ][ NeighborPos[i].x ].nFoundTreasureArround; }
}
}
}