fork(1) download
copy 
  1. /*
  2. puzzdra_solver
  3.  
  4. パズドラのルート解析プログラムです
  5.  
  6. コンパイラはMinGWを推奨します
  7.  
  8. コマンドは以下の通りです
  9. g++ -O2 -std=c++11 -fopenmp puzzdra_solver.cpp -o puzzdra_solver
  10.  
  11. なるべく少ない時間でなるべく大きいコンボを出したいです
  12.  
  13. printf("TotalDuration:%fSec\n", t_sum);
  14. printf("Avg.NormalCombo #:%f/%f\n", avg / (double)i, MAXCOMBO / (double)i);
  15.  
  16. これらが改善されればpull request受け付けます
  17.  
  18. チェック1：これを10コンボできるか
  19.  
  20. 962679
  21. 381515
  22. 489942
  23. 763852
  24. 917439
  25.  
  26. 914769
  27. 264812
  28. 379934
  29. 355886
  30. 951279
  31.  
  32. チェック2：1000盤面平均落ちコンボ数が9.20付近か
  33. チェック3：1000盤面平均コンボ数が理論値付近か
  34.  
  35. 全チェック達成したら合格
  36. */
  37. #pragma warning(disable:4710)
  38. #pragma warning(disable:4711)
  39. #pragma warning(disable:4820)
  40. #include <vector>
  41. #include <cfloat>
  42. #include <cstdio>
  43. #include <cstring>
  44. #include <climits>
  45. #include <ctime>
  46. #include <cstdlib>
  47. #include <cmath>
  48. #include <string>
  49. #include <iostream>
  50. #include <cstdint>
  51. #include <algorithm>
  52. #include <cassert>
  53. #include <random>
  54. #include <queue>
  55. #include <deque>
  56. #include <list>
  57. #include <map>
  58. #include <array>
  59. #include <chrono>
  60. #include <fstream>
  61. #include <functional>
  62. #include <unordered_map>
  63. #ifdef _OPENMP
  64. #include <omp.h>
  65. #endif
  66. #ifdef _MSC_VER
  67. #include <intrin.h>
  68. #endif
  69. using namespace std;
  70. #define DLT(ST,ED) ((double)((ED)-(ST))/CLOCKS_PER_SEC)//時間差分
  71. #define XX(PT)  ((PT)&15)
  72. #define YY(PT)  XX((PT)>>4)
  73. #define YX(Y,X) ((Y)<<4|(X))
  74. #define DIR 4//方向
  75. #define ROW 5//縦//MAX6
  76. #define COL 6//横//MAX7
  77. #define DROP 6//ドロップの種類//MAX9
  78. #define TRN  155//手数//MAX155
  79. #define STP YX(7,7)//無効手[無効座標]
  80. #define MAX_TURN 150//最大ルート長//MAX150
  81. #define BEAM_WIDTH 5000//ビーム幅//MAX200000
  82. #define PROBLEM 1000//問題数
  83. #define BONUS 10//評価値改善係数
  84. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  85. #define NODE_SIZE MAX(150,4*BEAM_WIDTH)
  86. typedef char F_T;//盤面型
  87. typedef char T_T;//手数型
  88. typedef unsigned long long ll;
  89. enum { EVAL_NONE = 0, EVAL_FALL, EVAL_SET, EVAL_FS, EVAL_COMBO };
  90. void init(int board[COL]); //初期配置生成関数
  91. void set2(int board[COL], int force); //空マスを埋める関数
  92. void show_board(int board[COL]); //盤面表示関数
  93. unsigned int rnd(int mini, int maxi); //整数乱数
  94. //上下左右に連結しているドロップを再帰的に探索していく関数
  95. int chain(int nrw, int ncl, int d, int board[COL], F_T chkflag[ROW][COL], F_T delflag[ROW][COL]);
  96. //int evaluate(int board[COL], int flag); //コンボ数判定関数
  97. //int sum_e(int board[COL]);//落とし有り、落ちコン無しコンボ数判定関数
  98. //int sum_evaluate(int board[COL]);//落としも落ちコンも有りコンボ数判定関数
  99. void operation(int board[COL], T_T route[TRN]); //スワイプ処理関数
  100.  
  101. int evaluate2(int board[COL], int flag, int* combo, ll* hash);//落とし減点評価関数
  102. int sum_e2(int board[COL], int* combo, ll* hash);//評価関数
  103.  
  104. ll xor128();//xorshift整数乱数
  105. ll zoblish_field[ROW][COL][DROP + 1];
  106.  
  107. int GetHeight(int x, int board[COL]);//高さを求める
  108.  
  109. #ifdef _MSC_VER
  110. int __builtin_clzll(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
  111. #endif // _MSC_VER
  112.  
  113. unsigned int bsr(unsigned int  v) { return 31 - __builtin_clzll(v); } // 最上位の1は下から数えて何ビット目か？
  114.  
  115. void check_operation(F_T field[ROW][COL],T_T route[TRN]);
  116. void set_field(int board[COL],F_T field[ROW][COL]);
  117. int chain2(int nrw, int ncl, int d, int board[COL],ll* chkflag, ll delflag);
  118. int iss_same(int board[COL],F_T field[ROW][COL]);
  119. void show_field(F_T field[ROW][COL]);
  120. void fall(int x, F_T field[ROW][COL]);
  121. void set(F_T field[ROW][COL], int force);
  122.  
  123. inline int Get(int x, int y, int board[COL]);//x,y座標のブロックの数字を取得
  124. inline void SetBit(int x, int y, int n, int board[COL]);//x,y座標のブロックをブロックnに変える
  125. inline void fall2(int x, int board[COL]); //ドロップの落下処理関数
  126.  
  127. struct node {//どういう手かの構造体
  128. 	T_T movei[TRN];//スワイプ移動座標
  129. 	int score;//評価値
  130. 	int combo;//コンボ数
  131. 	int nowC;//今どのx座標にいるか
  132. 	int nowR;//今どのy座標にいるか
  133. 	int prev;//1手前は上下左右のどっちを選んだか
  134. 	int prev_score;//1手前の評価値
  135. 	int improving;//評価値改善回数
  136. 	ll hash;//盤面のハッシュ値
  137. 	node() {//初期化
  138. 		this->score = 0;
  139. 		this->prev = -1;
  140. 		//memset(this->movei, STP, sizeof(this->movei));
  141. 	}
  142. 	bool operator < (const node& n)const {//スコアが高い方が優先される
  143. 		return score < n.score;
  144. 	}
  145. }fff[NODE_SIZE];
  146. struct Action {//最終的に探索された手
  147. 	int score;//コンボ数
  148. 	int maxcombo;//理論コンボ数
  149. 	T_T moving[TRN];//スワイプ移動座標
  150. 	Action() {//初期化
  151. 		this->score = 0;
  152. 		//memset(this->moving, STP, sizeof(this->moving));
  153. 	}
  154. };
  155.  
  156. inline int Get(int x, int y, int board[COL])
  157. {
  158. 	return ((board[x] >> ((y) * 4))& 15);
  159. }
  160.  
  161. inline void SetBit(int x, int y, int n, int board[COL])
  162. {
  163. 	int shift = ((y) * 4);
  164. 	board[x] &= (~(15 << shift));
  165. 	board[x] |= ((n) << shift);
  166. }
  167.  
  168. int GetHeight(int x, int board[COL])
  169. {
  170. 	if (board[x] == 0)
  171. 	{
  172. 		return 0;
  173. 	}
  174. 	else
  175. 	{
  176. 		int p = bsr(board[x]);
  177. 		p /= 4;
  178. 		p += 1;
  179. 		return p;
  180. 	}
  181. }
  182. Action BEAM_SEARCH(int f_board[COL]); //ルート探索関数
  183. double part1 = 0, part2 = 0, part3 = 0, part4 = 0, MAXCOMBO = 0;
  184. Action BEAM_SEARCH(int f_board[COL]) {
  185.  
  186. 	int stop = 0;//理論最大コンボ数
  187.  
  188. 	int drop[DROP + 1] = { 0 };
  189. 	for (int row = 0; row < ROW; row++) {
  190. 		for (int col = 0; col < COL; col++) {
  191. 			//if (1 <= f_field[row][col] && f_field[row][col] <= DROP) {
  192. 			int b = Get(col, row, f_board);
  193. 			if (1 <= b && b <= DROP) {
  194. 				drop[b]++;
  195. 			}
  196. 		}
  197. 	}
  198. 	for (int i = 1; i <= DROP; i++) {
  199. 		stop += drop[i] / 3;
  200. 	}
  201. 	MAXCOMBO += (double)stop;
  202.  
  203. 	deque<node>dque;
  204. 	double start, st;
  205. 	//1手目を全通り探索する
  206. 	dque.clear();
  207. 	for (int i = 0; i < ROW; i++) {
  208. 		for (int j = 0; j < COL; j++) {
  209. 			node cand;
  210. 			cand.nowR = ROW-1-i;//y座標
  211. 			cand.nowC = j;//x座標
  212. 			cand.prev = -1;//1手前はない
  213. 			cand.movei[0] = (T_T)YX(ROW-1-i, j);//1手目のyx座標
  214. 			for (int trn = 1; trn < TRN; trn++) {
  215. 				cand.movei[trn] = STP;
  216. 			}
  217. 			int ff_board[COL];
  218. 			memcpy(ff_board, f_board, sizeof(ff_board));
  219. 			int cmb;
  220. 			ll ha;
  221. 			cand.prev_score = sum_e2(ff_board, &cmb, &ha);
  222. 			cand.improving = 0;
  223. 			cand.hash = ha;
  224. 			dque.push_back(cand);
  225. 		}
  226. 	}         // L, U,D,R //
  227. 	int dx[DIR] = { -1, 0,0,1 },
  228. 		dy[DIR] = { 0,-1,1,0 };
  229. 	Action bestAction;//最善手
  230. 	int maxValue = 0;//最高スコア
  231.  
  232. 	bestAction.maxcombo = stop;
  233.  
  234. 	unordered_map<ll, bool> checkNodeList[ROW * COL];
  235.  
  236. 	//2手目以降をビームサーチで探索
  237. 	for (int i = 1; i < MAX_TURN; i++) {
  238. 		int ks = (int)dque.size();
  239. 		start = omp_get_wtime();
  240. #pragma omp parallel for private(st),reduction(+:part1,part4)
  241. 		for (int k = 0; k < ks; k++) {
  242. #ifdef _OPENMP
  243. 			if (i == 1 && k == 0) {
  244. 				printf("Threads[%d/%d]\n",
  245. 					omp_get_num_threads(),
  246. 					omp_get_max_threads());
  247. 			}
  248. #endif
  249. 			node temp = dque[k];//que.front(); que.pop();
  250. 			int temp_board[COL];
  251. 			memcpy(temp_board, f_board, sizeof(temp_board));
  252. 			operation(temp_board, temp.movei);
  253. 			for (int j = 0; j < DIR; j++) {//上下左右の4方向が発生
  254. 				node cand = temp;
  255. 				if (0 <= (cand.nowC + dx[j]) && (cand.nowC + dx[j]) < COL &&
  256. 					0 <= (cand.nowR + dy[j]) && (cand.nowR + dy[j]) < ROW) {
  257. 					if (cand.prev + j != 3) {
  258. 						int board[COL];//盤面
  259. 						memcpy(board, temp_board, sizeof(temp_board));//盤面をもどす
  260. 						int tmp = Get(cand.nowC, cand.nowR, board);
  261. 						SetBit(cand.nowC, cand.nowR, Get(cand.nowC + dx[j], cand.nowR + dy[j], board), board);
  262. 						SetBit(cand.nowC + dx[j], cand.nowR + dy[j], tmp, board);
  263. 						cand.nowC += dx[j];
  264. 						cand.nowR += dy[j];
  265. 						cand.movei[i] = (T_T)YX(cand.nowR, cand.nowC);
  266. 						st = omp_get_wtime();
  267. 						int cmb;
  268. 						ll ha;
  269. 						cand.score = sum_e2(board, &cmb, &ha);
  270. 						cand.combo = cmb;
  271. 						cand.hash = ha;
  272. 						part1 += omp_get_wtime() - st;
  273. 						cand.prev = j;
  274. 						st = omp_get_wtime();
  275. 						//#pragma omp critical
  276. 											//{ pque.push(cand); }
  277. 						fff[(4 * k) + j] = cand;
  278. 						part4 += omp_get_wtime() - st;
  279. 					}
  280. 					else {
  281. 						cand.combo = -1;
  282. 						fff[(4 * k) + j] = cand;
  283. 					}
  284. 				}
  285. 				else {
  286. 					cand.combo = -1;
  287. 					fff[(4 * k) + j] = cand;
  288. 				}
  289. 			}
  290. 		}
  291. 		part2 += omp_get_wtime() - start;
  292. 		start = omp_get_wtime();
  293. 		dque.clear();
  294. 		vector<pair<int, int> >vec;
  295. 		int ks2 = 0;
  296. 		for (int j = 0; j < 4 * ks; j++) {
  297. 			if (fff[j].combo != -1) {
  298. 				if (fff[j].score > fff[j].prev_score) { fff[j].improving = fff[j].improving + 1; }
  299. 				fff[j].prev_score = fff[j].score;
  300. 				vec.push_back(make_pair(fff[j].score + (BONUS * fff[j].improving), j));
  301. 				ks2++;
  302. 			}
  303. 		}
  304. 		sort(vec.begin(), vec.end());
  305. 		int push_node = 0;
  306. 		for (int j = 0; push_node < BEAM_WIDTH && j < ks2; j++) {
  307. 			node temp = fff[vec[ks2 - 1 - j].second];
  308. 			if (maxValue < temp.combo) {//コンボ数が増えたらその手を記憶する
  309. 				maxValue = temp.combo;
  310. 				bestAction.score = maxValue;
  311. 				memcpy(bestAction.moving, temp.movei, sizeof(temp.movei));
  312. 				//コンボ数が理論値になったらreturn
  313. 				if (temp.combo == stop) { return bestAction; }
  314. 			}
  315. 			if (i < MAX_TURN - 1) {
  316. 				int pos = (temp.nowR * COL) + temp.nowC;
  317. 				if (!checkNodeList[pos][temp.hash]) {
  318. 					checkNodeList[pos][temp.hash] = true;
  319. 					dque.push_back(temp);
  320. 					push_node++;
  321. 				}
  322. 			}
  323. 		}
  324. 		part3 += omp_get_wtime() - start;
  325. 	}
  326. 	return bestAction;
  327. }
  328. void show_board(int board[COL]) {
  329. 	for (int i = ROW - 1; i >= 0; i--) {
  330. 		for (int j = 0; j < COL; j++) {
  331. 			printf("%d", Get(j, i, board));
  332. 		}
  333. 		printf("\n");
  334. 	}
  335. }
  336.  
  337. void show_field(F_T field[ROW][COL]) {
  338. 	for (int i = 0; i < ROW; i++) {
  339. 		for (int j = 0; j < COL; j++) {
  340. 			printf("%d", field[i][j]);
  341. 		}
  342. 		printf("\n");
  343. 	}
  344. }
  345. inline void fall2(int x, int board[COL]) {
  346. 	int n = 0;
  347. 	int offset = 0;//空きマスが途中に何個あるか
  348. 	for (int i = 0; i < ROW; i++)
  349. 	{
  350. 		int b = (board[x] & (15 << ((i)* 4)));//map[x]のi番目の高さまでの値をbに格納
  351. 		if (b == 0)//空きマスなら
  352. 		{
  353. 			offset += 4;
  354. 		}
  355. 		else
  356. 		{
  357. 			n |= (b >> offset);
  358. 		}
  359. 	}
  360. 	board[x] = n;
  361. }
  362. void fall(int x, F_T field[ROW][COL]) {
  363. int tgt;
  364. 		for (tgt = ROW - 1; tgt >= 0 && field[tgt][x] != 0; tgt--);
  365. 		for (int i = tgt - 1; i >= 0; i--) {
  366. 			if (field[i][x] != 0) {
  367. 				F_T c = field[i][x];
  368. 				field[i][x] = 0;
  369. 				field[tgt][x] = c;
  370. 				tgt--;
  371. 			}
  372. 		}
  373. }
  374. void init(int board[COL]) { set2(board, !0); }
  375. void set2(int board[COL], int force) {
  376. 	for (int i = 0; i < ROW; i++) {
  377. 		for (int j = 0; j < COL; j++) {
  378. 			if (Get(j, i, board) == 0 || force) {//空マスだったらうめる
  379. 				int n = rnd(force ? 0 : 1, DROP);//1-DROPの整数乱数
  380. 				SetBit(j, i, n, board);
  381. 			}
  382. 		}
  383. 	}
  384. }
  385. void set(F_T field[ROW][COL], int force) {
  386. 	for (int i = 0; i < ROW; i++) {
  387. 		for (int j = 0; j < COL; j++) {
  388. 			if (field[i][j] == 0 || force) {//空マスだったらうめる
  389. 				field[i][j] = (F_T)rnd(force ? 0 : 1, DROP);//1-DROPの整数乱数
  390. 			}
  391. 		}
  392. 	}
  393. }
  394. int chain(int nrw, int ncl, int d, F_T field[ROW][COL],
  395. 	F_T chkflag[ROW][COL], F_T delflag[ROW][COL]) {
  396. 	int count = 0;
  397. #define CHK_CF(Y,X) (field[Y][X] == d && chkflag[Y][X]==0 && delflag[Y][X] > 0)
  398. 	//連結している同じ色の消去ドロップが未探索だったら
  399. 	if (CHK_CF(nrw, ncl)) {
  400. 		++count; //連結ドロップ数の更新
  401. 		chkflag[nrw][ncl]=1;//探索済みにする
  402. 			//以下上下左右に連結しているドロップを再帰的に探索していく
  403. 		if (0 < nrw && CHK_CF(nrw - 1, ncl)) {
  404. 			count += chain(nrw - 1, ncl, d, field, chkflag, delflag);
  405. 		}
  406. 		if (nrw < ROW - 1 && CHK_CF(nrw + 1, ncl)) {
  407. 			count += chain(nrw + 1, ncl, d, field, chkflag, delflag);
  408. 		}
  409. 		if (0 < ncl && CHK_CF(nrw, ncl - 1)) {
  410. 			count += chain(nrw, ncl - 1, d, field, chkflag, delflag);
  411. 		}
  412. 		if (ncl < COL - 1 && CHK_CF(nrw, ncl + 1)) {
  413. 			count += chain(nrw, ncl + 1, d, field, chkflag, delflag);
  414. 		}
  415. 	}
  416. 	return count;
  417. }
  418. int chain2(int nrw, int ncl, int d, int board[COL],
  419. 	ll* chkflag, ll delflag) {
  420. 	int count = 0;
  421. #define CHK_CF2(Y,X) (Get(X,Y,board) == d && !((*chkflag) & (1ll<<(((Y)*COL)+X))) && (delflag & (1ll<<((Y)*COL+X))) != 0)
  422. 	//連結している同じ色の消去ドロップが未探索だったら
  423. 	if (CHK_CF2(nrw, ncl)) {
  424. 		++count; //連結ドロップ数の更新
  425. 		(*chkflag) |= (1ll << ((nrw) * COL + ncl)); //探索済みにする
  426. 			//以下上下左右に連結しているドロップを再帰的に探索していく
  427. 		if (0 < nrw && CHK_CF2(nrw - 1, ncl)) {
  428. 			count += chain2(nrw - 1, ncl, d, board, chkflag, delflag);
  429. 		}
  430. 		if (nrw < ROW - 1 && CHK_CF2(nrw + 1, ncl)) {
  431. 			count += chain2(nrw + 1, ncl, d, board, chkflag, delflag);
  432. 		}
  433. 		if (0 < ncl && CHK_CF2(nrw, ncl - 1)) {
  434. 			count += chain2(nrw, ncl - 1, d, board, chkflag, delflag);
  435. 		}
  436. 		if (ncl < COL - 1 && CHK_CF2(nrw, ncl + 1)) {
  437. 			count += chain2(nrw, ncl + 1, d, board, chkflag, delflag);
  438. 		}
  439. 	}
  440. 	return count;
  441. }
  442. int evaluate(F_T field[ROW][COL], int flag) {
  443. 	int combo = 0;
  444.  
  445. 	while (1) {
  446. 		int cmb = 0;
  447. 		F_T chkflag[ROW][COL] = { 0 };
  448. 		F_T delflag[ROW][COL] = { 0 };
  449. 		for (int row = 0; row < ROW; row++) {
  450. 			for (int col = 0; col < COL; col++) {
  451. 				if (col <= COL - 3 && field[row][col] == field[row][col + 1] && field[row][col] == field[row][col + 2] && field[row][col] > 0) {
  452. 					delflag[row][col] = field[row][col];
  453. 					delflag[row][col + 1] = field[row][col];
  454. 					delflag[row][col + 2] = field[row][col];
  455. 				}
  456. 				if (row <= ROW - 3 && field[row][col] == field[row + 1][col] && field[row][col] == field[row + 2][col] && field[row][col] > 0) {
  457. 					delflag[row][col] = field[row][col];
  458. 					delflag[row + 1][col] = field[row][col];
  459. 					delflag[row + 2][col] = field[row][col];
  460. 				}
  461. 			}
  462. 		}
  463. 		for (int row = 0; row < ROW; row++) {
  464. 			for (int col = 0; col < COL; col++) {
  465. 				if (delflag[row][col] > 0) {
  466. 					if (chain(row, col, field[row][col], field, chkflag, delflag) >= 3) {
  467. 						cmb++;
  468. 					}
  469. 				}
  470. 			}
  471. 		}
  472. 		combo += cmb;
  473. 		//コンボが発生しなかったら終了
  474. 		if (cmb == 0 || 0 == (flag & EVAL_COMBO)) { break; }
  475. 		for (int row = 0; row < ROW; row++) {
  476. 			for (int col = 0; col < COL; col++) {
  477. 				//コンボになったドロップは空になる
  478. 				if (delflag[row][col] > 0) { field[row][col] = 0; }
  479. 			}
  480. 		}
  481.  
  482. 		if (flag & EVAL_FALL){
  483. 		for(int x=0;x<COL;x++){
  484. 		fall(x,field);
  485. 		}
  486. 		}//落下処理発生
  487. 		if (flag & EVAL_SET){set(field, 0);}//落ちコン発生
  488.  
  489. 	}
  490. 	return combo;
  491. }
  492.  
  493. int evaluate2(int board[COL], int flag, int* combo, ll* hash) {
  494. 	int ev = 0;
  495. 	*combo = 0;
  496. 	ll ha = 0;
  497. 	int oti = 0;
  498. 	while (1) {
  499. 		int cmb = 0;
  500. 		int cmb2 = 0;
  501. 		ll chkflag = 0;
  502. 		ll delflag = 0;
  503. 		for (int row = ROW - 1; row >= 0; row--) {
  504. 			for (int col = 0; col < COL; col++) {
  505. 				int num = Get(col, row, board);
  506. 				if (oti == 0) {
  507. 					ha ^= zoblish_field[row][col][num];
  508. 				}
  509. 				if (col <= COL - 3 && Get(col + 1, row, board) == num && Get(col + 2, row, board) == num && num > 0) {
  510. 					delflag |= (1ll << (((row) * COL) + col));
  511. 					delflag |= (1ll << (((row) * COL) + col + 1));
  512. 					delflag |= (1ll << (((row) * COL) + col + 2));
  513. 				}
  514. 				if (row >= 2 && Get(col, row - 1, board) == num && Get(col, row - 2, board) == num && num > 0) {
  515. 					delflag |= (1ll << (((row) * COL) + col));
  516. 					delflag |= (1ll << (((row - 1) * COL) + col));
  517. 					delflag |= (1ll << (((row - 2) * COL) + col));
  518. 				}
  519. 			}
  520. 		}
  521.  
  522. 		F_T cnt[DROP + 1] = { 0 };
  523. 		F_T drop[DROP + 1][ROW * COL][2] = { 0 };
  524.  
  525. 		for (int row = ROW - 1; row >= 0; row--) {
  526. 			for (int col = 0; col < COL; col++) {
  527. 				int num = Get(col, row, board);
  528. 				drop[num][cnt[num]][0] = (F_T)row;
  529. 				drop[num][cnt[num]][1] = (F_T)col;
  530. 				cnt[num]++;
  531. 				if ((delflag & (1ll << (((row) * COL) + col))) != 0) {
  532. 					int c = chain2(row, col, num, board, &chkflag, delflag);
  533. 					if (c >= 3) {
  534. 						cmb++;
  535. 						if (c == 3) { cmb2 += 30; }
  536. 						else { cmb2 += 20; }
  537. 					}
  538. 				}
  539. 			}
  540. 		}
  541. 		F_T erase_x[COL] = {0};
  542. 		for (int i = 1; i <= DROP; i++) {
  543. 			for (int j = 0; j < cnt[i] - 1; j++) {
  544. 				int d1 = (int)drop[i][j][0];
  545. 				int d2 = (int)drop[i][j][1];
  546. 				int d3 = (int)drop[i][j + 1][0];
  547. 				int d4 = (int)drop[i][j + 1][1];
  548. 				int add = max(d1 - d3, d3 - d1) + max(d2 - d4, d4 - d2);
  549. 				add += add;
  550. 				add /= 3;
  551. 				cmb2 -= add;
  552. 				if ((delflag & (1ll << (((d1) * COL) + d2))) != 0) {
  553. 					SetBit(d2, d1, 0, board);
  554. 					erase_x[d2]=1;
  555. 				}
  556. 				if ((delflag & (1ll << (((d3) * COL) + d4))) != 0) {
  557. 					SetBit(d4, d3, 0, board);
  558. 					erase_x[d4]=1;
  559. 				}
  560. 			}
  561. 		}
  562. 		(*combo) += cmb;
  563. 		ev += cmb2;
  564. 		//コンボが発生しなかったら終了
  565. 		if (cmb == 0 || 0 == (flag & EVAL_COMBO)) { break; }
  566. 		oti++;
  567. 		if (flag & EVAL_FALL){//落下処理発生
  568. 		for(int x=0;x<COL;x++){
  569. 		if(erase_x[x]==1){
  570. 		fall2(x,board);
  571. 		}
  572. 		}
  573. 		}
  574. 		if (flag & EVAL_SET) {
  575. 			set2(board, 0);
  576. 		}//落ちコン発生
  577.  
  578. 	}
  579. 	ev += oti;
  580. 	(*hash) = ha;
  581. 	return ev;
  582. }
  583. int sum_e2(int board[COL], int* combo, ll* hash) {//落とし有り、落ちコン無し評価関数
  584. 	return evaluate2(board, EVAL_FALL | EVAL_COMBO, combo, hash);
  585. }
  586. int sum_e(F_T field[ROW][COL]) {//落とし有り、落ちコン無しコンボ数判定関数
  587. 	return evaluate(field, EVAL_FALL | EVAL_COMBO);
  588. }
  589. int sum_evaluate(F_T field[ROW][COL]) {//落としも落ちコンも有りコンボ数判定関数
  590. 	return evaluate(field, EVAL_FS | EVAL_COMBO);
  591. }
  592. //移動した後の盤面を生成する関数
  593. void operation(int board[COL], T_T route[TRN]) {
  594. 	int prw = (int)YY(route[0]), pcl = (int)XX(route[0]), i;
  595. 	for (i = 1; i < MAX_TURN; i++) {
  596. 		if (route[i] == STP) { break; }
  597. 		//移動したら、移動前ドロップと移動後ドロップを交換する
  598. 		int row = (int)YY(route[i]), col = (int)XX(route[i]);
  599. 		int c = Get(pcl, prw, board);
  600. 		SetBit(pcl, prw, Get(col, row, board), board);
  601. 		SetBit(col, row, c, board);
  602. 		prw = row, pcl = col;
  603. 	}
  604. }
  605. unsigned int rnd(int mini, int maxi) {
  606. 	static mt19937 mt((int)time(0));
  607. 	uniform_int_distribution<int> dice(mini, maxi);
  608. 	return dice(mt);
  609. }
  610. ll xor128() {//xorshift整数乱数
  611. 	static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
  612. 	ll rt = (rx ^ (rx << 11));
  613. 	rx = ry; ry = rz; rz = rw;
  614. 	return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
  615. }
  616. void check_operation(F_T field[ROW][COL],T_T route[TRN]){
  617. int prw = ROW-1-((int)YY(route[0]));
  618. int pcl = (int)XX(route[0]);
  619. int i;
  620. 	for (i = 1; i < MAX_TURN; i++) {
  621. 		if (route[i] == STP) { break; }
  622. 		//移動したら、移動前ドロップと移動後ドロップを交換する
  623. 		int row= ROW-1-((int)YY(route[i]));
  624. 		int col = (int)XX(route[i]);
  625. 		int c =field[prw][pcl];
  626. 		field[prw][pcl]=field[row][col];
  627. 		field[row][col]=c;
  628. 		prw = row, pcl = col;
  629. 	}
  630. }
  631. void set_field(int board[COL],F_T field[ROW][COL]){
  632.  
  633. for (int i = ROW - 1; i >= 0; i--) {
  634. 		for (int j = 0; j < COL; j++) {
  635. 			int num=Get(j,i,board);
  636. 			field[ROW-1-i][j]=num;
  637. 		}
  638. 	}
  639.  
  640. }
  641.  
  642. int iss_same(int board[COL],F_T field[ROW][COL]){
  643.  
  644. for (int i = ROW - 1; i >= 0; i--) {
  645. 		for (int j = 0; j < COL; j++) {
  646. 			int num=Get(j,i,board);
  647. 			if(num!=field[ROW-1-i][j]){return 0;}
  648. 		}
  649. 	}
  650. 	return 1;
  651. }
  652.  
  653. int main() {
  654.  
  655.  
  656. 	int i, j, k;
  657.  
  658. 	for (i = 0; i < ROW; ++i) {
  659. 		for (j = 0; j < COL; ++j) {
  660. 			for (k = 0; k <= DROP; k++) {
  661. 				zoblish_field[i][j][k] = xor128();
  662. 			}
  663. 		}
  664. 	}
  665.  
  666. 	double avg = 0;//平均コンボ数
  667. 	double start;
  668. 	double t_sum = 0;
  669. 	double oti_avg = 0;//平均落ちコンボ数
  670.  
  671. 	for (i = 0; i < PROBLEM; i++) {//PROBLEM問解く
  672. 		printf("input:No.%d/%d\n", i + 1, PROBLEM);
  673. 		//init(f_field); set(f_field, 0);//初期盤面生成
  674. 		//show_field(f_field);//盤面表示
  675. 		int board[COL];
  676. 		init(board); set2(board, 0);
  677. 		show_board(board);
  678. 		int f_board[COL];
  679. 		/*
  680. 		for (j = 0; j < ROW; j++) {
  681. 			string s = "";
  682. 			cin >> s;
  683. 			for (k = 0; k < COL; k++) {
  684. 				SetBit(k,ROW-1-j,s[k]-'0',board);
  685. 			}
  686. 		}
  687. 		*/
  688. 		memcpy(f_board, board, sizeof(board));
  689. 		F_T field[ROW][COL];
  690. 		set_field(board,field);
  691. 		start = omp_get_wtime();
  692. 		Action tmp = BEAM_SEARCH(board);//ビームサーチしてtmpに最善手を保存
  693. 		double diff = omp_get_wtime() - start;
  694. 		t_sum += diff;
  695. 		printf("(x,y)=(%d,%d)", XX(tmp.moving[0]), YY(tmp.moving[0]));
  696. 		for (j = 1; j < MAX_TURN; j++) {//y座標は下にいくほど小さくなる
  697. 			if (tmp.moving[j] == STP) { break; }
  698. 			if (XX(tmp.moving[j]) == XX(tmp.moving[j - 1]) + 1) { printf("R"); } //"RIGHT"); }
  699. 			if (XX(tmp.moving[j]) == XX(tmp.moving[j - 1]) - 1) { printf("L"); } //"LEFT"); }
  700. 			if (YY(tmp.moving[j]) == YY(tmp.moving[j - 1]) + 1) { printf("U"); } //"UP"); }
  701. 			if (YY(tmp.moving[j]) == YY(tmp.moving[j - 1]) - 1) { printf("D"); } //"DOWN"); }
  702. 		} printf("\n");
  703. 		operation(f_board, tmp.moving);
  704. 		check_operation(field,tmp.moving);
  705. 		printf("output:No.%d/%d\n", i + 1, PROBLEM);
  706. 		show_board(f_board);
  707. 		int res=iss_same(f_board,field);
  708. 		if(res==0){
  709. 		for(int t=0;t<10;t++){
  710. 		printf("akan");
  711. 		}
  712. 		printf("show_field invalid\n");
  713. 		show_field(field);
  714. 		break;
  715. 		}
  716. 		int combo = sum_e(field);
  717. 		if(combo!=tmp.score){
  718. 		for(int t=0;t<10;t++){
  719. 		printf("akan");
  720. 		}
  721. 		printf("score invalid\n");
  722. 		break;
  723. 		}
  724. 		//int oti = sum_evaluate(oti_field);
  725. 		printf("Normal:%d/%dCombo\n", tmp.score, tmp.maxcombo);
  726. 		printf("elapsed time:%fSec\n", diff);
  727. 		printf("------------\n");
  728. 		//avg += (double)combo;
  729. 		//oti_avg += (double)oti;
  730. 		avg += (double)tmp.score;
  731. 	}
  732. 	printf("TotalDuration:%fSec\n", t_sum);
  733. 	printf("Avg.NormalCombo #:%f/%f\n", avg / (double)i, MAXCOMBO / (double)i);
  734. 	printf("Avg.OtiCombo #:%f\n", oti_avg / (double)i);
  735. 	printf("p1:%f,p2:%f,p3:%f,p4:%f\n", part1, part2, part3, part4);
  736. 	j = getchar();
  737. 	return 0;
  738.  
  739. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘Action BEAM_SEARCH(int*)’:
prog.cpp:239:11: error: ‘omp_get_wtime’ was not declared in this scope
   start = omp_get_wtime();
           ^~~~~~~~~~~~~
prog.cpp:239:11: note: suggested alternative: ‘timer_gettime’
   start = omp_get_wtime();
           ^~~~~~~~~~~~~
           timer_gettime
prog.cpp: In function ‘int main()’:
prog.cpp:691:11: error: ‘omp_get_wtime’ was not declared in this scope
   start = omp_get_wtime();
           ^~~~~~~~~~~~~
prog.cpp:691:11: note: suggested alternative: ‘timer_gettime’
   start = omp_get_wtime();
           ^~~~~~~~~~~~~
           timer_gettime
stdout
copy 
Standard output is empty
https://ideone.com/LlkjT3
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!