#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#include	<assert.h>
#include	<stdarg.h>

//#define	RELEASE

/************************************************************/
//型定義
typedef	int		s32;
typedef	char	s8;

//駅構造体
typedef struct _station Station;
struct _station{
	char	name[ 32 ];		//駅の名前
	Station	**linkStations;	//繋がっている駅
	s32	link_num;			//その数
} ;

//ゲーム管理クラス
class Game{
private:
	Station	*goalStation;	//目標駅
	Station	*nowStation;	//現在の駅
	static Game	*m_instance;	//インスタンス

	s32		m_state_flag;	//状態フラグ
	Station	*m_prevStation;	//前の駅（いけるかな？用）

	//フラグ
	enum{
		eARRIVE_FLAG = 0x1,
	}eFLAG;

public:
	static Game* GetInstance(){ 
		if( m_instance == NULL ) m_instance = new Game();
		return m_instance;
	}

	void	InitAll( void );			//初期化
	void	FreeAll( void );			//開放
	void	GameMain( void );
	void	Dice( void );				//サイコロ
	bool	Process( Station *station, s32 value );	//進む（再帰）
	bool	Process2( Station *start_station, s32 value ); //進む

	void	RegistStation( s32 mode );	// 駅登録
	s32		GetMostShortDistance( Station *start, Station *goal ); //最短距離

	void	FlagON( s32 value ){ m_state_flag |= value; }
	void	FlagOFF( s32 value ){ m_state_flag &= ~value; }
	s32		GetFlag(){ return m_state_flag; }

};
Game* Game::m_instance = NULL;

/************************************************************/
//駅名列挙
enum _name{
	OSAKA = 0,
	KYOTO,
	HYOGO,
	NARA,
	WAKAYAMA,
	SHIGA,
	MIE,
	HAWAI,
} eNAME;

//駅の数
#define	STATION_NUM	(8)

//最短距離の試行回数
#define	MAX_TRY	(99)

// ログ出力
static	bool OutPutFlag = false;
void dprintf(const char *format, ...)
{
	va_list ap;

	va_start(ap, format);
	if( OutPutFlag )printf(format, ap);
	va_end(ap);
}

/************************************************************/

//グローバル宣言
Station	g_station[ STATION_NUM ];	//駅

//関数プロトタイプ

/************************************************************/

//------------------------------------------------------//
//	初期化
//------------------------------------------------------//
void	Game::InitAll( void )
{
	Station *work;	//作業用
	s32	i, j;

	//駅名
	s8 *names[] = { "大阪", "京都", "兵庫", "奈良", "和歌山", "滋賀", "三重", "ハワイ" };

	//繋がっている駅の数
	s32	link_num[] = { 5, 4, 2, 4, 3, 2, 3, 1 };

	//繋がっている駅の定義
	s32 links[][ 5 ] = {
		{ KYOTO, HYOGO, NARA, WAKAYAMA, HAWAI },	//大阪
		{ OSAKA, HYOGO, NARA, SHIGA },		//京都
		{ OSAKA, KYOTO },					//兵庫
		{ OSAKA, KYOTO, WAKAYAMA, MIE },	//奈良
		{ OSAKA, NARA, MIE },				//和歌山
		{ KYOTO, MIE },						//滋賀
		{ NARA, WAKAYAMA, SHIGA },			//三重
		{ OSAKA },							//ハワイ
	};

	//構造体に代入
	work = g_station;
	for( i = 0; i < STATION_NUM; i++, work++ ){
		strcpy_s( work->name, names[ i ] );
		work->link_num = link_num[ i ];

		//繋がっている駅格納用のメモリ確保
		work->linkStations = new Station* [ work->link_num ];
		
		if( work->linkStations == NULL ){
			assert( !"メモリ確保失敗。" );
		}

		for( j = 0; j < work->link_num; j++ ){
			s32	link_station = links[ i ][ j ];
			work->linkStations[ j ] = &g_station[ link_station ];
		}
	}

	//確認用ログ出力
	work = g_station;
	for( i = 0; i < STATION_NUM; i++, work++ ){
		printf("[%s]-->", work->name );
		for( j = 0; j < work->link_num; j++ ){
			printf("%s ", work->linkStations[ j ]->name );
		}
		printf("\n");
	}

	//スタートとゴール地点(デフォルト)
	this->nowStation = &g_station[ OSAKA ];
	this->goalStation = &g_station[ HAWAI ];

	//メンバ初期化
	m_state_flag = 0;
}


//------------------------------------------------------//
//	終了
//------------------------------------------------------//
void	Game::FreeAll( void )
{
	Station *work;	//作業用
	s32	i;

	//構造体に代入
	work = g_station;
	for( i = 0; i < STATION_NUM; i++, work++ ){
		//メモリ開放
		delete []work->linkStations;
	}
}

//------------------------------------------------------//
//	ゲーム開始
//------------------------------------------------------//
void	Game::GameMain( void )
{
	bool end_flag = false;
	s32	command;
	s8 sbuf[ 32 ];

	while( !end_flag ){
		printf("\n現在地[%s] 目的地[%s]\n", this->nowStation->name, this->goalStation->name );
		printf("[0]サイコロ [1]最短距離確認 [2]現在地設定 [3]目的地設定 [4]終了 \n" );
		command = atoi( gets_s( sbuf ) );
		switch( command ){
		case 0:
			Dice();
			break;
		case 1:
			// 最短経路を求める
			{
				s32 distance = GetMostShortDistance( this->nowStation, this->goalStation );
				printf("\n////////////////////////////////////////\n\n");
				printf("あと%dマス\n\n", distance );
			}
			break;
		case 2:
			RegistStation( 0 );
			break;
		case 3:
			RegistStation( 1 );
			break;
		case 4:
			end_flag = true;
			break;
		}
	}
}

//------------------------------------------------------//
//	最短経路を求める(MAX_TRYマスまで確認)
//------------------------------------------------------//
s32		Game::GetMostShortDistance( Station *start, Station *goal )
{
	s32	i;

	for( i = 0; i < MAX_TRY; i++ ){
		this->FlagOFF( eARRIVE_FLAG );
		bool ret = Process( start, i );
		if( ret )return i;
	}
	return -1;
}

//------------------------------------------------------//
//	登録
//------------------------------------------------------//
void	Game::RegistStation( s32 mode )
{
	s32	no;
	s8 sbuf[ 32 ];

	printf("[0]大阪 [1]京都 [2]兵庫 [3]奈良 [4]和歌山 [5]滋賀 [6]三重 [7]ハワイ\n");
	no = atoi( gets_s( sbuf ) );
	if( mode == 0 ){
		this->nowStation = &g_station[ no ];
	}else{
		this->goalStation = &g_station[ no ];
	}
}

//------------------------------------------------------//
//	サイコロ
//------------------------------------------------------//
void	Game::Dice( void )
{
	s32	num;
	s8	sbuf[ 32 ];

	printf("サイコロの目は？--->");
	num = atoi( gets_s( sbuf ) );

	//マスを進める

	Station *start = this->nowStation;

	//進行
	this->m_prevStation = start;
	this->FlagOFF( eARRIVE_FLAG );
	bool ret = Process2( start, num );

	if( ret ){
		printf("\n**************************************\n");
		printf("\n駅到着します。\n");
	}else{
		printf("\n駅到着しません。\n");
	}
}

//------------------------------------------------------//
//	進む(再帰ver)
//	@par 現在の駅
//		 目
//------------------------------------------------------//
bool	Game::Process( Station *station, s32 value )
{
	s32	i, ret;

	//値が０なら終了地点
	if( value == 0 ){
		//その駅は目的の駅か？
		if( station == this->goalStation ){
			printf("\n////////////////////////////////////////\n");
			printf("[%s]", station->name );
			this->FlagON( eARRIVE_FLAG );
			return true;
		}
	}

	//次の駅
	if( value > 0 ){
		value--;
		for( i = 0; i < station->link_num; i++ ){
			//ただし、前の駅には行けない
			if( station->linkStations[ i ] != this->m_prevStation ){
				this->m_prevStation = station;
				ret = Process( station->linkStations[ i ], value );
				if( ret ){
					//駅表示
					printf("<--[%s]", station->name );
					return true;
				}
			}
		}
	}
	return false;
}

//------------------------------------------------------//
//	進む(NOT再帰ver)
//	@par 最初の駅
//		 目
//------------------------------------------------------//
bool	Game::Process2( Station *start_station, s32 value )
{
	s32	i;
	Station *station, *next, **saveStation;	// 作業用、次の駅、保持用
	s32	*save, val, index;

	station = start_station;

	// インデックス保存用
	save = new s32 [ value + 1 ];
	if( !save )exit(1);
	for( i = 0; i < value+1; i++ ){
		save[ i ] = 0;
	}
	val = value;

	// 駅保存
	saveStation = new Station* [value+1];
	if( !saveStation )exit(1);
	saveStation[ value ] = start_station;

	dprintf("start\n");

	// サイコロが0の時
	if( val == 0 ){
		if( start_station == goalStation ) return true;
		else return false;
	}

	while( true ){
		// 終了条件
		if( station == start_station && save[ value ] >= start_station->link_num ){
			dprintf("探索終了。発見できず。save[ val ]=%d val=%d\n", save[ val ], val );
			break;
		}

		// 次の駅がなし
		if( station->link_num <= save[ val ] ){
			dprintf("次の駅が見つからないので、一階層戻ります。基点[%s]\n", saveStation[ val+1 ] );
			save[ val ] = 0; //クリア
			val++;
			save[ val ]++;
			if( save[ val ] > start_station->link_num ){
				//end
			}else{
				station = saveStation[ val ];
				m_prevStation = saveStation[ val+1 ];
			}
			continue;
		}

		index = save[ val ];

		//ただし、直前の駅には行けない
		if( station->linkStations[ index ] == this->m_prevStation ){
			dprintf("今の駅[%s]から前の駅[%s]にはいけません。\n", station->name, this->m_prevStation->name );
			// スキップ
			if( station->link_num > save[ val ] ){
				//dprintf("スキップ\n");
				save[ val ]++;
				continue;
			}
		}
		else{
			Station *temp = this->m_prevStation;
			// 保存
			this->m_prevStation = station;

			// 進む
			next = station->linkStations[ index ];
			val--;
			saveStation[ val ] = next;
			dprintf("%s->%sをチェック。", station->name, next->name );

			// 目的の駅か？
			if( val == 0 && next == this->goalStation && this->goalStation != temp ){
				dprintf("目的の駅[%s]に到着。", next->name );
				this->FlagON( eARRIVE_FLAG );
				break;
			}else{
				// 行き止まり？
				if( val == 0 ){
					dprintf("手止まり。\n");
					save[ val ] = 0; //クリア
					//戻る
					val++;
					save[ val ]++;
					saveStation[ val ] = station;
					this->m_prevStation = temp;
					continue;
				}

				// まだサイコロの目が残っているならその駅からさらにリンク
				else{
					dprintf("さらにリンク。\n");
					station = next;
					continue;
				}
			}
		}
	}
	if( this->GetFlag() & eARRIVE_FLAG ){
		// 軌跡表示
		printf("\n");
		printf("**************************************\n");
		for( i = value; i >= 0; i-- ){
			if( i == 0 ){
				printf("%s",saveStation[i]->name);
			}else{
				printf("%s->",saveStation[i]->name);
			}
		}

		delete saveStation;
		delete []save;
		return true;
	}else{
		delete saveStation;
		delete []save;
		return false;
	}
}

//------------------------------------------------------//
//	メイン
//------------------------------------------------------//
int	main( void )
{
	//初期化
	Game::GetInstance()->InitAll();

	//ゲーム開始
	Game::GetInstance()->GameMain();

	//終了手続き
	Game::GetInstance()->FreeAll();

	return 0;
}