• UVA-1343 旋转游戏 题解答案代码 算法竞赛入门经典第二版

    GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

    题目其实不难，但是耗费了我较多时间。

    这种题关键就是在于找到约束条件，我在DFS的基础上，试了很多种策略：

    1. 对3种数字，每种数字递归遍历一次，这样每次只需要关注一种数字的变化，情况更少。

    2. 使用一个long long类型的数字作为map的key，key表示这种数字在图形中分别的位置，value表示在第几步访问过。如果重复访问且步数更长，则不继续递归。

    3. 使用剪枝策略，认为不符合情况结点不继续遍历。（但是我想的剪枝方法不合理，使用了之后是错误的，在最后有给出）

    4. 迭代加深搜索，一层一层更深的查找。适用于本题次数最少的要求。

    5. 乐观估价函数：在中心每个点的值不对的情况下，每个点都至少需要一次移动才能正确。因此估价函数为 不正确的点数+现有的步数 <= 要求的最大步数。

    上述的方法是结合使用的，一开始没想到估价函数，一直在剪枝策略中纠结，然后一直超时。最后换成了估价函数，时间瞬间缩短了。

    虽然移动的可能性是无限的，但是最多的移动次数也就是十几次。

    AC代码

    1. #include
    2. #include 
    3. #include
    4.  
    5. #define MAXLEN 15
    6.  
    7. using namespace std;
    8.  
    9. int arr[24];
    10. int arrCon[4][7];
    11. // 是否访问过的记录
    12. map<long long, int> mp;
    13. // 记录三种数字完成时的移动情况 
    14. char moves[3][MAXLEN + 5];
    15. // 移动数组的长度 
    16. int moveCount[3];
    17. // 每个移动数组代表的移动类型（可能并不是下表所指示的那个） 
    18. int moveType[3];
    19.  
    20. // 从输入数据转换为四数组模式 
    21. void convertArr() {
    22. 	int i;
    23. 	arrCon[0][0] = arr[0]; arrCon[1][0] = arr[1];
    24. 	arrCon[0][1] = arr[2]; arrCon[1][1] = arr[3];
    25. 	for(i = 0; i < 7; ++i) arrCon[2][i] = arr[4 + i];
    26. 	arrCon[0][2] = arr[6]; arrCon[1][2] = arr[8];
    27. 	arrCon[0][3] = arr[11]; arrCon[1][3] = arr[12];
    28. 	for(i = 0; i < 7; ++i) arrCon[3][i] = arr[13 + i];
    29. 	arrCon[0][4] = arr[15]; arrCon[1][4] = arr[17];
    30. 	arrCon[0][5] = arr[20]; arrCon[1][5] = arr[21];
    31. 	arrCon[0][6] = arr[22]; arrCon[1][6] = arr[23];
    32. }
    33.  
    34. // 对一个数组移动位置 type->0 往大移动 type->1 往小移动
    35. void moveArr(int *arrSrc, int type) {
    36. 	int t, i;
    37. 	if(type == 0) {
    38. 		t = arrSrc[6];
    39. 		for(i = 6; i > 0; --i) arrSrc[i] = arrSrc[i-1];
    40. 		arrSrc[0] = t;
    41. 	} else {
    42. 		t = arrSrc[0];
    43. 		for(i = 0; i < 6; ++i) arrSrc[i] = arrSrc[i+1];
    44. 		arrSrc[6] = t;
    45. 	}
    46. }
    47.  
    48. // 按照某个方向移动  flag->1 移动 flag->0 恢复移动 
    49. void moveStep(int num, bool flag) {
    50. 	bool type;
    51. 	switch(num) {
    52. 		case 0:
    53. 		case 5:
    54. 			type = num < 4 ? 1 : 0;
    55. 			type = flag ? type : !type;
    56. 			moveArr(arrCon[0], type);
    57. 			arrCon[2][2] = arrCon[0][2];
    58. 			arrCon[3][2] = arrCon[0][4];
    59. 			break;
    60. 		case 1:
    61. 		case 4:
    62. 			type = num < 4 ? 1 : 0;
    63. 			type = flag ? type : !type;
    64. 			moveArr(arrCon[1], type);
    65. 			arrCon[2][4] = arrCon[1][2];
    66. 			arrCon[3][4] = arrCon[1][4];
    67. 			break;
    68. 		case 2:
    69. 		case 7:
    70. 			type = num < 4 ? 0 : 1;
    71. 			type = flag ? type : !type;
    72. 			moveArr(arrCon[2], type);
    73. 			arrCon[0][2] = arrCon[2][2];
    74. 			arrCon[1][2] = arrCon[2][4];
    75. 			break;
    76. 		case 3:
    77. 		case 6:
    78. 			type = num < 4 ? 0 : 1;
    79. 			type = flag ? type : !type;
    80. 			moveArr(arrCon[3], type);
    81. 			arrCon[0][4] = arrCon[3][2];
    82. 			arrCon[1][4] = arrCon[3][4];
    83. 			break;
    84. 	}
    85. }
    86.  
    87. // 是否成功 返回成功的字符 否则0 
    88. int isArrive() {
    89. 	int num = arrCon[0][2];
    90. 	if(arrCon[0][3] != num || arrCon[0][4] != num || arrCon[1][2] != num || arrCon[1][3] != num) 
    91. 		return 0;
    92. 	if(arrCon[1][4] != num || arrCon[2][3] != num || arrCon[3][3] != num)
    93. 		return 0;
    94. 	return num;
    95. }
    96.  
    97. // 根据数字在四数组中的位置，转换为0-27的数字数组 
    98. long long getArrPos(int num) {
    99. 	int i, j;
    100. 	long long sum = 0;
    101. 	for(i = 0; i < 4; ++i) {
    102. 		for(j = 0; j < 7; ++j) {
    103. 			if(arrCon[i][j] == num) {
    104. 				if(i < 2) {
    105. 					sum = (sum << 5) + i * 7 + j;
    106. 				} else {
    107. 					if(j == 2 || j == 4) continue;
    108. 					sum = (sum << 5) + i * 7 + j;
    109. 				}
    110. 			}
    111. 		}
    112. 	}
    113. 	return sum;
    114. }
    115.  
    116. // 剪枝
    117. bool shouldMove(int num, int step) {
    118. 	switch(step) {
    119. 		case 0:
    120. 			if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;
    121. 			break;
    122. 		case 1:
    123. 			if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;
    124. 			break;
    125. 		case 2:
    126. 			if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;
    127. 			break;
    128. 		case 3:
    129. 			if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;
    130. 			break;
    131. 		case 4:
    132. 			if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;
    133. 			break;
    134. 		case 5:
    135. 			if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;
    136. 			break;
    137. 		case 6:
    138. 			if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;
    139. 			break;
    140. 		case 7:
    141. 			if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;
    142. 			break;
    143. 	}
    144. 	return false;
    145. }
    146.  
    147. // 估价函数 true代表有机会 false代表没机会 
    148. bool hvalue(int num, int stepCount, int k) {
    149. 	int i, j, value = 0;
    150. 	for(i = 0; i < 4; ++i) {
    151. 		if(arrCon[i][3] != num) value += 1;
    152. 	}
    153. 	if(arrCon[0][2] != num) value += 1;
    154. 	if(arrCon[0][4] != num) value += 1;
    155. 	if(arrCon[1][2] != num) value += 1;
    156. 	if(arrCon[1][4] != num) value += 1;
    157. 	return stepCount + value < k;
    158. }
    159.  
    160. //递归寻找 
    161. int getValue(int num, int stepCount, int k) {
    162. 	int resArr = isArrive();
    163. 	if(resArr) {
    164. 		moveType[num - 1] = resArr;
    165. 		return stepCount;
    166. 	}
    167. 	if(stepCount >= k) return 0;
    168. 	if(!hvalue(num, stepCount, k))	return 0;
    169. 	int i, count, res;
    170. 	long long sum; 
    171. 	// printf(" ------ %d\n", stepCount);
    172. 	for(i = 0; i < 8; ++i) {
    173. 		// if(!shouldMove(num, i)) continue;
    174. 		// 移动
    175. 		moveStep(i, true);
    176. 		// printf(" ----------- %d\n", isFind(num));
    177. 		sum = getArrPos(num);
    178. 		count = mp[sum];
    179. 		if(!count || count > stepCount) {
    180. 			mp[sum] = stepCount;
    181. 			// 记录步骤 
    182. 			moves[num-1][stepCount] = i;
    183. 			// 访问子节点
    184. 			res = getValue(num, stepCount+1, k);
    185. 			if(res) {
    186. 				// 复位
    187. 				moveStep(i, false); 
    188. 				return res;
    189. 			}
    190. 		}
    191. 		// 复位
    192. 		moveStep(i, false);
    193. 	}
    194. 	return 0;
    195. }
    196.  
    197. int getRes(int k) {
    198. 	int i, j, mini, minV;
    199. 	for(i = 0; i < 3; ++i) {
    200. 		mp.clear();
    201. 		long long sum = getArrPos(i+1);
    202. 		mp[sum] = 0;
    203. 		moveCount[i] = getValue(i+1, 0, k);
    204. 		if(moveCount[i] > 0) k = moveCount[i];
    205. 		// printf("-- %d %d %d \n", k, i, moveCount[i-1]);
    206. 		// moves[i-1][moveCount[i-1]] = 0;
    207. 	}
    208. 	minV = MAXLEN + 10;
    209. 	mini = -1;
    210. 	for(i = 0; i < 3; ++i) {
    211. 		if(moveCount[i] == 0) continue;
    212. 		// printf( "[]%d\n", moveCount[i]);
    213. 		if(minV > moveCount[i]) {
    214. 			minV = moveCount[i];
    215. 			mini = i;
    216. 		} else if(minV == moveCount[i]) {
    217. 			if(strcmp(moves[mini], moves[i]) > 0) {
    218. 				minV = moveCount[i];
    219. 				mini = i;
    220. 			}
    221. 		}
    222. 	}
    223. 	return mini;
    224. }
    225.  
    226. int main() {
    227. 	int i, j, k;
    228. 	while(1) {
    229. 		if(scanf("%d", &arr[0]) != 1 || arr[0] == 0) break;
    230. 		for(i = 1; i < 24; ++i) {
    231. 			scanf("%d", &arr[i]);
    232. 		}
    233. 		convertArr();
    234. 		int resType = isArrive();
    235. 		if(resType) {
    236. 			printf("No moves needed\n");
    237. 			printf("%d\n", resType);
    238. 			continue;
    239. 		}
    240. 		for(i = 1; i < MAXLEN; ++i) {
    241. 			k = getRes(i);
    242. 			if(k >= 0) break;
    243. 		}
    244. 		if(moveCount[k] == 0) {
    245. 			printf("No moves needed\n");
    246. 		} else {
    247. 			for(i = 0; i < moveCount[k]; ++i) {
    248. 				printf("%c", moves[k][i] + 'A');
    249. 			}
    250. 			putchar('\n'); 
    251. 		}
    252. 		printf("%d\n", moveType[k]);
    253. 	}
    254. 	return 0;
    255. }

    错误的剪枝策略：（不要使用））

    1. // 错误的剪枝策略，
    2. bool shouldMove(int num, int step) {
    3. 	switch(step) {
    4. 		case 0:
    5. 			if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;
    6. 			break;
    7. 		case 1:
    8. 			if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;
    9. 			break;
    10. 		case 2:
    11. 			if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;
    12. 			break;
    13. 		case 3:
    14. 			if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;
    15. 			break;
    16. 		case 4:
    17. 			if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;
    18. 			break;
    19. 		case 5:
    20. 			if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;
    21. 			break;
    22. 		case 6:
    23. 			if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;
    24. 			break;
    25. 		case 7:
    26. 			if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;
    27. 			break;
    28. 	}
    29. 	return false;
    30. }

  • 相关阅读:
    智能巡检软件怎么选？企业设备管理需要做什么？
    [附源码]Python计算机毕业设计Django个性化产品服务管理系统论文
    基于时空注意力融合网络的城市轨道交通假期短时客流预测
    HBase学习笔记
    全球元宇宙市场投融资总额超320亿元 资本争相涌入 元宇宙探索仍在路上
    聊天、会议、多媒体一体化：多平台支持的即时通讯系统 | 开源日报 No.44
    亚马逊云科技顾凡解读云计算助力初创快速抢滩生成式AI新风口
    主流网络协议
    负载均衡的算法(静态算法与动态算法)
    B032-服务器 Tomcat JavaWeb项目 Servlet
  • 原文地址：https://blog.csdn.net/qq278672818/article/details/132932231