fork(10) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // 横:6,縦:5
  4. // ドロップの種類:7
  5. // 0:空 1:火 2:水 3:木 4:光 5:闇 6:回復
  6.  
  7. enum{
  8. 	EMPTY = 0,FIRE,WATER,WOOD,LIGHT,DARK,HEART,
  9. };
  10. const int H = 5,W = 6;
  11. const int N = 7;
  12. const int D = 4;
  13. // DOWN RIGHT UP LEFT
  14. vector<string> direction = {"DOWN","RIGHT", "UP", "LEFT"};
  15. int dx[] = {0,1,0,-1};
  16. int dy[] = {1,0,-1,0};
  17.  
  18. class ZobristHash{
  19. public:
  20. 	int table[H*W][N];
  21. 	ZobristHash(){
  22. 		for(int i=0;i<H*W;i++){
  23. 			for(int j=0;j<N;j++){
  24. 				table[i][j] = rand();
  25. 			}
  26. 		}
  27. 	}
  28. 	int hash(int* board){
  29. 		int h = 0;
  30. 		for(int i=0;i<H*W;i++){
  31. 			if(board[i] != 0){
  32. 				int j = board[i];
  33. 				h ^= table[i][j];
  34. 			}
  35. 		}
  36. 		return h;
  37. 	}
  38. };
  39.  
  40. struct State{
  41. public:
  42. 	double value_ = -1;
  43. 	int* board_;
  44. 	int* comboed_board_ = NULL;
  45. 	int point_x_, point_y_;
  46. 	int combo_counter_ = -1;
  47. 	int turns_ = 0;
  48. 	list<int> move_process_;
  49.  
  50. 	// ランダム盤面とポイントを生成
  51. 	State(){
  52. 		board_ = new int[H*W];
  53. 		for(int i=0;i<H*W;i++){
  54. 			board_[i] = rand()%7+1;
  55. 		}
  56. 		point_x_ = rand()%W;
  57. 		point_y_ = rand()%H;
  58. 		value_ = GetValue();
  59. 	}
  60. 	// コピー
  61. 	State(int* bd,int px,int py,int turns,list<int> move_process){
  62. 		board_ = new int[H*W];
  63. 		CopyBoard(bd,board_);
  64. 		point_x_ = px;
  65. 		point_y_ = py;
  66. 		value_ = GetValue();
  67.  
  68. 		turns_ = turns;
  69. 		move_process_ = move_process;
  70. 	}
  71.  
  72. 	~State(){
  73. 		delete[] board_;
  74. 		delete[] comboed_board_;
  75. 	}
  76.  
  77. 	// 盤面の評価値を返す
  78. 	double GetValue(){
  79. 		if(value_ != -1)return value_;
  80. 		double val = 0.0;
  81. 		int combo_counter = GetComboCounter();
  82.  
  83. 		int two_continuous_counter = 0;
  84. 		for(int i=0;i<H;i++){
  85. 			for(int j=0;j<W;j++){
  86. 				if( j < W-1 && comboed_board_[i*W+j] == comboed_board_[i*W+j+1] && comboed_board_[i*W+j] != 0){
  87. 					two_continuous_counter++;
  88. 				}
  89. 				if( i < H-1 && comboed_board_[i*W+j] == comboed_board_[(i+1)*W+j] && comboed_board_[i*W+j] != 0){
  90. 					two_continuous_counter++;
  91. 				}
  92. 			}
  93. 		}
  94.  
  95. 		val = combo_counter * 100 + two_continuous_counter * 5;
  96.  
  97. 		// if(turns_ > 20)return value_ = 0;
  98. 		return value_ = val;
  99. 	}
  100. 	// 次の全てのStateを得る
  101. 	vector<State*> GetAllNextStates(){
  102. 		vector<State*> next_states;
  103. 		for(int i=0;i<D;i++){
  104. 			int next_point_x_ = point_x_ + dx[i];
  105. 			int next_point_y_ = point_y_ + dy[i];
  106. 			if(IsOutOfBoard(next_point_x_,next_point_y_))continue;
  107. 			swap( board_[point_y_*W+point_x_], board_[next_point_y_*W+next_point_x_] );
  108. 			move_process_.push_back(i);
  109. 			next_states.push_back(new State(board_, next_point_x_, next_point_y_, turns_ + 1,move_process_));
  110. 			swap( board_[point_y_*W+point_x_], board_[next_point_y_*W+next_point_x_] );
  111. 			move_process_.pop_back();
  112. 		}
  113. 		return next_states;
  114. 	}
  115. 	int GetComboCounter(){
  116. 		if(combo_counter_ == -1)return combo_counter_ = SimulateCombo();
  117. 		return combo_counter_;
  118. 	}
  119.  
  120.  
  121. 	// コンボをシミュレートしてコンボ数を返す，comboed_board_にコンボ後の盤面が入る
  122. 	int SimulateCombo(){
  123. 		// コンボ後盤面の領域確保
  124. 		comboed_board_ = new int[H*W];
  125. 		for(int i=0;i<H*W;i++)
  126. 			comboed_board_[i] = board_[i];
  127.  
  128. 		int combo_counter = 0;
  129. 		for(;;){
  130. 			int temp = SimulateComboAndDrop();
  131. 			combo_counter += temp;
  132. 			if(temp == 0)break;
  133. 		}
  134. 		return combo_counter;
  135. 	}
  136. 	// コンボして下に詰める
  137. 	int SimulateComboAndDrop(){
  138. 		int combo_counter = 0;
  139. 		// コンボをシミュレートする
  140. 		// コンボ部分に10加算
  141. 		PrepareCombo();
  142. 		// 10以上の部分で繋がっている部分を0にする
  143. 		for(int i=0;i<H;i++)for(int j=0;j<W;j++){
  144. 			if(PrepareComboDFS( j, i, comboed_board_[i*W+j]))combo_counter++;
  145. 		}
  146. 		// ドロップを下に詰める
  147. 		for(int j=0;j<W;j++){
  148. 			int empty_point = 0;
  149. 			for(int i=H-1;i>=0;i--){
  150. 				if( comboed_board_[i*W+j] == 0 && empty_point < i )empty_point = i;
  151. 				else if(comboed_board_[i*W+j] != 0 && empty_point > i){
  152. 					comboed_board_[empty_point*W+j] = comboed_board_[i*W+j];
  153. 					comboed_board_[i*W+j] = 0;
  154. 					empty_point--;
  155. 				}
  156. 			}
  157. 		}
  158. 		return combo_counter;
  159. 	}
  160. 	void PrepareCombo(){
  161. 		const int flag = 10;
  162. 		// 横3つ以上のものに印
  163. 		for(int i=0;i<H;i++){
  164. 			int counter = 1;
  165. 			for(int j=1;j<=W;j++){
  166. 				if( W == j || comboed_board_[i*W+j]%flag != comboed_board_[i*W+j-1]%flag || comboed_board_[i*W+j] == EMPTY){
  167. 					if(counter >= 3){
  168. 						for(int k=j-counter;k<j;k++){
  169. 							comboed_board_[i*W + k] += flag;
  170. 						}
  171. 					}
  172. 					counter = 1;
  173. 				}
  174. 				else counter++;
  175. 			}
  176. 		}
  177. 		// 縦3つ以上のものに印
  178. 		for(int i=0;i<W;i++){
  179. 			int counter = 1;
  180. 			for(int j=1;j<=H;j++){
  181. 				if( H == j || comboed_board_[j*W+i]%flag != comboed_board_[(j-1)*W+i]%flag || comboed_board_[j*W+i] == EMPTY ){
  182. 					if(counter >= 3){
  183. 						for(int k=j-counter;k<j;k++){
  184. 							comboed_board_[k*W+i] += flag;
  185. 						}
  186. 					}
  187. 					counter = 1;
  188. 				}
  189. 				else counter++;
  190. 			}
  191. 		}
  192. 	}
  193. 	bool PrepareComboDFS(int x,int y,int color){
  194. 		if(comboed_board_[y*W+x] < 10)return false;
  195. 		comboed_board_[y*W+x] = 0;
  196. 		for(int i=0;i<D;i++){
  197. 			int nx = x + dx[i], ny = y + dy[i];
  198. 			if(IsOutOfBoard(nx,ny))continue;
  199. 			if( comboed_board_[ny*W+nx] < 10 || color%10 != comboed_board_[ny*W+nx]%10)continue;
  200. 			PrepareComboDFS(nx,ny,color);
  201. 		}
  202. 		return true;
  203. 	}
  204.  
  205. 	// 盤面内にポイントがあるか
  206. 	bool IsOutOfBoard(int px, int py){
  207. 		if(px < 0 || py < 0 || px >= W || py >= H)return true;
  208. 		else return false;
  209. 	}
  210. 	// 盤面のディープコピー用
  211. 	void CopyBoard(int* from_board_,int* to_board_){
  212. 		for(int i=0;i<H*W;i++)
  213. 			to_board_[i] = from_board_[i];
  214. 	}
  215. 	// 盤面を標準出力に表示
  216. 	void OutputBoard(){
  217. 		for(int i=0;i<H;i++){
  218. 			for(int j=0;j<W;j++){
  219. 				cout << board_[i*W+j] << " ";
  220. 			}
  221. 			cout << endl;
  222. 		}
  223. 	}
  224. 	void OutputComboedBoard(){
  225. 		if(comboed_board_ == NULL){
  226. 			SimulateCombo();
  227. 		}
  228. 		for(int i=0;i<H;i++){
  229. 			for(int j=0;j<W;j++){
  230. 				cout << comboed_board_[i*W+j] << " ";
  231. 			}
  232. 			cout << endl;
  233. 		}
  234. 	}
  235. 	void OutputInfo(){
  236. 		cout << "turns" << endl;
  237. 		cout << turns_ << endl;
  238. 		cout << "point" << endl;
  239. 		cout << point_x_ << " " << point_y_ << endl;
  240. 		cout << "value" << endl;
  241. 		cout << GetValue() << endl;
  242. 		cout << "board" << endl;
  243. 		OutputBoard();
  244. 		cout << "comboed board" << endl;
  245. 		OutputComboedBoard();
  246. 		cout << "process" << endl;
  247. 		OutputMoveProcess();
  248. 	}
  249. 	void OutputMoveProcess(){
  250. 		for(auto it=move_process_.begin();it!=move_process_.end();it++){
  251. 			cout << *it << " ";
  252. 		}cout << endl;
  253. 	}
  254. 	bool operator<(const State &state)const{
  255. 		return value_ < state.value_;
  256. 	}
  257. };
  258.  
  259. struct StateCompare{
  260. 	bool operator()(State* s1, State* s2)const{
  261. 		return *s1 < *s2;
  262. 	}
  263. };
  264.  
  265. int main(void){
  266. 	srand(time(NULL));
  267. 	ZobristHash zb;
  268.  
  269. 	// 初期盤面をランダムで生成
  270. 	int* init_board = new int[H*W];
  271. 	cout << "init board" << endl;
  272. 	for(int i=0;i<H;i++){
  273. 		for(int j=0;j<W;j++){
  274. 			init_board[i*W+j] = rand()%6+1;
  275. 			cout << init_board[i*W+j] << " ";
  276. 		}cout << endl;
  277. 	}
  278. 	cout << endl;
  279.  
  280. 	cout << "Start Searching" << endl;
  281. 	int MaxTurn = 12,beam_breath = 40000;
  282. 	set<int> searched_states;
  283. 	priority_queue<State*,vector<State*>,StateCompare> now_states_pq;
  284.  
  285. 	// 初期状態の生成
  286. 	for(int i=0;i<H;i++)for(int j=0;j<W;j++){
  287. 		State* state = new State(init_board,j,i,0,list<int>());
  288. 		now_states_pq.push(state);
  289. 		searched_states.insert(zb.hash(state->board_));
  290. 	}
  291.  
  292. 	// ビームサーチ
  293. 	for(int t=0; t < MaxTurn; t++){
  294. 		cout << "|";cout.flush();
  295. 		priority_queue<State*,vector<State*>,StateCompare> next_states_pq;
  296. 		for(int i=0; i < beam_breath; i++){
  297. 			if(now_states_pq.empty())break;
  298. 			State* now_state = now_states_pq.top();now_states_pq.pop();
  299. 			next_states_pq.push(now_state);
  300.  
  301. 			// 次の状態の生成
  302. 			vector<State*> next_states = now_state->GetAllNextStates();
  303. 			for(int j=0;j<next_states.size();j++){
  304. 				State* next_state = next_states[j];
  305. 				// ハッシュ値計算
  306. 				int state_hash_code = zb.hash(next_state->board_);
  307. 				// 既に探索済みであれば，探索しない
  308. 				if(searched_states.find(state_hash_code) != searched_states.end())continue;
  309. 				searched_states.insert(state_hash_code);
  310. 				next_states_pq.push(next_state);
  311. 			}
  312. 		}
  313. 		now_states_pq = next_states_pq;
  314.  
  315. 		// 現在の最大の状態を出力
  316. 		/*
  317. 		State* state = now_states_pq.top();
  318. 		cout << t << " Top State" << endl;
  319. 		cout << state->turns_ << " " << state->GetValue() << " " << next_states_pq.size() << endl;
  320. 		state->OutputMoveProcess();
  321. 		cout << endl;
  322. 		*/
  323. 	}
  324. 	cout << endl << "End Searching" << endl << endl;
  325.  
  326. 	State* best_state = now_states_pq.top();
  327. 	int px = best_state->point_x_;
  328. 	int py = best_state->point_y_;
  329. 	list<int> move_process = best_state->move_process_;
  330. 	cout << "final board" << endl;
  331. 	best_state->OutputBoard();
  332. 	cout << "Combo: " << best_state->GetComboCounter() << endl;
  333. 	for(auto it=move_process.begin();it!=move_process.end();it++){
  334. 		px -= dx[*it];
  335. 		py -= dy[*it];
  336. 	}
  337. 	cout << px << " " << py << endl;
  338. 	for(auto it=move_process.begin();it!=move_process.end();it++){
  339. 		cout << direction[*it] << " ";
  340. 		px -= dx[*it];
  341. 		py -= dy[*it];
  342. 	}cout << endl;
  343.  
  344. 	return 0;
  345. }
  346.  
Success #stdin #stdout 2.4s 196736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
init board
1 6 4 4 6 6 
2 5 1 1 5 1 
2 1 6 5 2 2 
6 2 5 3 3 6 
5 6 1 4 4 2 

Start Searching
||||||||||||
End Searching

final board
1 6 1 4 6 6 
2 5 6 1 5 1 
2 5 4 5 2 2 
2 1 1 3 3 6 
6 5 6 4 4 2 
Combo: 5
2 0
DOWN DOWN DOWN DOWN LEFT LEFT UP RIGHT UP RIGHT
https://ideone.com/MbxQOR
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!