• UVA-1602 网格动物 题解答案代码 算法竞赛入门经典第二版

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

    使用dfs遍历所有情况，再去重即可。

    遍历部分

    遍历的时候需要注意：

    1. 这其实并不能算是dfs，因为普通的dfs是一直走到尽头，然后再逐渐退出，走下一条路。到最后的路径是一条线。但是这个题目生成的图形却可以分叉。因此，递归一次dfs时，要循环遍历当前所有的节点，让所有的节点都可以分叉进行。

    2. 如果直接遍历所有情况，那么肯定是超时的。我是这样做的：

    我一开始尝试了从w*h区域的每个点开始遍历，遇到墙就返回。这样其实存在大量的重复，会重复生成一样的图形。我后面改造成了直接从（1， 1）点开始遍历。并不真实的设立一个墙。在生成的过程中，如果碰到这个图像的宽和高大于区域的大小，那么认为这个区域放不下这个图形，就退出。这中间出现坐标负值也是正常的。

    3. 用上面的方法之后，还是有较多的超时。因此我们继续优化。这时候我们设定一个中间图形是否遍历过的set。假设该图形或者该图形的旋转，平移和镜像在set中存在了，就说明已经遍历过了，就不在往下进行。这样能够很大的缩小情况的种类。比如：[(1,1), (1,2)] 和 [(1,1), (2,1)] 等等都属于重复图形，也就是说，dfs的第二层依旧只有一个结点。这样节约的时间是很多的。

    4. 用了上面的方法后，还是超时。但是即使输出全部的情况下，在本地电脑中也是比较快的，大概一两分钟左右。由于情况不多（不超过1000中情况），因此直接打表更适合。即我们在本地算出结果，把结果直接写在代码里。我直接在代码中写了n=10情况下的所有输出，其他情况下还是实时计算的。这样最后AC了。

    如何对图形进行的旋转，平移和镜像

    除了遍历之外，还有一个注意的点就是，如何对图形进行的旋转，平移和镜像。且能在set中标识这个图形。

    1. 标识图形

    由于每个点的的最大坐标为(1-10,1-10），最多10个点，因此标识所有情况需要 10^20。64位存不下。换一种表示法，用起点加转向，就是100*4^9， 64位存下绰绰有余。但是我们并不是一条路径，可以有分叉，因此这种方式做不到。

    还有一个问题就是，存在set中的结构要保证唯一性，即同样一个图形，如果点的位置不一致，也可以找到。这时候我们就想到用set存储单个图形。然后单个图形的set元素是一个int，里面的值是100 * x + y。由于set是排好序的，因此我们的点在里面就是天然排序的，先按照x值排序，在按照y值排序。这样可以保证点不会因为位置交换了而判断为两个图形。

    当然，100 * x + y的方法在遇到负值是有很大的问题，后面我又进行了改进。网络上还有人用其他方法可以存储单个点的，也可以参考。假设我们的点是（1， -1），那么值是-99。还原回点的时候，就变成了（0， -99）。

    我的解决方案是，让值保持整数: 100 * x + y  ——>  100 *(x+20) + y + 20。由于坐标最大为10，因此计算的结果肯定是正的，还原回来也肯定是正的。

    2. 平移

    平移非常简单，我们让以x坐标和y坐标最小值为基准，设为1。其他的点平移这个差值即可。

    这个平移的作用实际上是标准化，即将在不同位置的图形，都平移到一个位置，如果他是一个图形，那么平移之后位置是一致的。

    3. 旋转图形

    我们只需要实现转90度的方法即可。转两次就是180，三次就是270。

    向右转90度，对于图形来说，坐标变化就是：（x， y） -> （y， -x）。画个图试一下就能看出规律了。因此，每次旋转时我们执行这个变化即可。

    旋转之后还要平移一次。

    4. 镜像图形

    我们随便横向镜像和纵向镜像都可以，因此横向镜像后转90度就变为纵向镜像了。镜像更简单，x或者y的符号变一下即可。这时候我们注意到一点：

    如果我们的点坐标是0，镜像完还是0，那肯定是不正确的。因此坐标从1开始，即1 - 10。1的前一个点是-1，我们没有0这个点。这时候平移和遍历就出问题了：

    1和-1中间的差值是2不是1，我们如果正常遍历， 会走到0这个点。我们平移的时候如果图形中间穿过0这条线，那么减的值是不正确的。因此，我们要相应做处理，如果坐标值碰到0，根据情况设为1或者-1。平移的时候区分中间有0和没有0的情况。

    AC代码

    1. #include
    2. #include
    3. #include
    4. #include
    5.  
    6. using namespace std;
    7.  
    8. int n, w, h;
    9. int steps[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    10. // 数量
    11. int num;
    12. set<int> seArr, seTemp;
    13. setint>> se;
    14. int arrTemp[10][2];
    15. // 该状态是否访问过 
    16. setint>> seFlag;
    17.  
    18. int tenTable[1000] = {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,16,68,108,117,118,0,0,0,21,277,842,1226,1329,1338,1339,0,0,21,287,1847,3234,3773,3876,3885,3886,0,1,277,1847,2376,4003,4542,4645,4654,4655,0,16,842,3234,4003,4003,4542,4645,4654,4655,0,68,1226,3773,4542,4542,4542,4645,4654,4655,0,108,1329,3876,4645,4645,4645,4645,4654,4655,0,117,1338,3885,4654,4654,4654,4654,4654,4655,1,118,1339,3886,4655,4655,4655,4655,4655,4655};
    19.  
    20. void getXY(int res, int &x, int &y) {
    21. 	x = res / 100 - 20;
    22. 	y = res % 100 - 20;
    23. }
    24.  
    25. void output(set<int> &setTemp) {
    26. 	int x, y;
    27. 	for(auto ip = setTemp.begin(); ip != setTemp.end(); ++ip) {
    28. 		getXY(*ip, x, y);
    29. 		printf("[%d,%d] ", x, y);
    30. 	}
    31. 	putchar('\n');
    32. }
    33.  
    34. int setXY(int x, int y) {
    35. 	return (x + 20) * 100 + y + 20;
    36. }
    37.  
    38. // 规范化 最小的x为 1 最小的y为 1
    39. void standard(int (* arr)[2], int ntemp) {
    40. 	int i;
    41. 	int minX = arr[0][0], minY = arr[0][1];
    42. 	for(i = 1; i < ntemp; ++i) {
    43. 		if(arr[i][0] < minX) minX = arr[i][0];
    44. 		if(arr[i][1] < minY) minY = arr[i][1];
    45. 	}
    46. 	for(i = 0; i < ntemp; ++i) {
    47. 		if(arr[i][0] * minX > 0)
    48. 			arr[i][0] = arr[i][0] - minX + 1;
    49. 		else
    50. 			arr[i][0] = arr[i][0] - minX;
    51. 		if(arr[i][1] * minY > 0)
    52. 			arr[i][1] = arr[i][1] - minY + 1;
    53. 		else
    54. 			arr[i][1] = arr[i][1] - minY;
    55. 	}
    56. }
    57.  
    58. // 点的数组转为set 
    59. void arr2Set(set<int> &setTemp, int (* arr)[2], int ntemp) {
    60. 	setTemp.clear();
    61. 	for(int i = 0; i < ntemp; ++i) {
    62. 		setTemp.insert(setXY(arr[i][0], arr[i][1]));
    63. 	}
    64. }
    65.  
    66. // set转为点的数组
    67. void set2Arr(set<int> &setTemp, int (* arr)[2]) {
    68. 	int i = 0;
    69. 	for(auto ip = setTemp.begin(); ip != setTemp.end(); ++ip, ++i) {
    70. 		getXY(*ip, arr[i][0], arr[i][1]);
    71. 	}
    72. }
    73.  
    74. // 向右旋转90度
    75. void turnRight(int (* arr)[2], int ntemp) {
    76. 	int j;
    77. 	for(int i = 0; i < ntemp; ++i) {
    78. 		j = arr[i][1];
    79. 		arr[i][1] = -arr[i][0];
    80. 		arr[i][0] = j;
    81. 	}
    82. }
    83.  
    84. // 镜像反转
    85. void reserveArr(int (* arr)[2], int ntemp) {
    86. 	for(int i = 0; i < ntemp; ++i) {
    87. 		arr[i][0] = -arr[i][0]; 
    88. 	}
    89. }
    90.  
    91. void judge(set<int> &setTemp) {
    92. 	if(se.count(setTemp)) return;
    93. 	++num;
    94. 	se.insert(seTemp);
    95. }
    96.  
    97. bool isBumpWall(set<int> &setTemp) {
    98. 	auto ip = setTemp.begin();
    99. 	int x, y;
    100. 	getXY(*ip, x, y);
    101. 	int minX = x, minY = y, maxX = x, maxY = y;
    102. 	for(ip = setTemp.begin(); ip != setTemp.end(); ++ip) {
    103. 		getXY(*ip, x, y);
    104. 		if(x < minX) minX = x;
    105. 		if(y < minY) minY = y;
    106. 		if(x > maxX) maxX = x;
    107. 		if(y > maxY) maxY = y;
    108. 	}
    109. 	x = maxX - minX - (maxX * minX < 0 ? 1 : 0);
    110. 	y = maxY - minY - (maxY * minY < 0 ? 1 : 0);
    111. 	if(((x >= w || y >= h) && (x >= h || y >= w)) || x + y >= n) return true;
    112. 	return false; 
    113. } 
    114.  
    115. // 该模式的几种变形是否访问过 
    116. bool findModel(int (* arr)[2], set<int> &setTemp, int ntemp) {
    117. 	if(seFlag.count(setTemp)) return true;
    118. 	int i;
    119. 	for(i = 0; i < 3; ++i) {
    120. 		// 转90度
    121. 		turnRight(arrTemp, ntemp);
    122. 		standard(arrTemp, ntemp);
    123. 		arr2Set(setTemp, arrTemp, ntemp);
    124. 		if(seFlag.count(setTemp)) return true;
    125. 	}
    126. 	// 镜像反转
    127. 	reserveArr(arrTemp, ntemp);
    128. 	for(i = 0; i < 4; ++i) {
    129. 		// 转90度
    130. 		if(i != 0) turnRight(arrTemp, ntemp);
    131. 		standard(arrTemp, ntemp);
    132. 		arr2Set(setTemp, arrTemp, ntemp);
    133. 		if(seFlag.count(setTemp)) return true;
    134. 	}
    135. 	return false; 
    136. }
    137.  
    138. void dfs(int count) {
    139. 	++count;
    140. 	int i, x, y, xi, yi, resi;
    141. 	for(auto ip = seArr.begin(); ip != seArr.end(); ++ip) {
    142. 		getXY(*ip, x, y);
    143. 		for(i = 0; i < 4; ++i) {
    144. 			xi = steps[i][0] + x;
    145. 			yi = steps[i][1] + y;
    146. 			if(xi == 0) {
    147. 				if(steps[i][0] > 0) xi = 1;
    148. 				if(steps[i][0] < 0) xi = -1;
    149. 			}
    150. 			if(yi == 0) {
    151. 				if(steps[i][1] > 0) yi = 1;
    152. 				if(steps[i][1] < 0) yi = -1;
    153. 			}
    154. 			resi = setXY(xi, yi);
    155. 			if(seArr.count(resi)) continue;
    156. 			seArr.insert(resi);
    157. 			set2Arr(seArr, arrTemp);
    158. 			standard(arrTemp, count);
    159. 			arr2Set(seTemp, arrTemp, count);
    160. 			if(!isBumpWall(seArr) && !findModel(arrTemp, seTemp, count)) {
    161. 				// 设置访问标记 
    162. 				seFlag.insert(seTemp);
    163. 				if(count == n) judge(seTemp);
    164. 				else dfs(count);
    165. 			}
    166. 			seArr.erase(resi);
    167. 		}
    168. 	}
    169. }
    170.  
    171. int compute() {
    172. 	num = 0;
    173. 	se.clear();
    174. 	seFlag.clear();
    175. 	seArr.clear();
    176. 	seArr.insert(setXY(1, 1));
    177. 	dfs(1);
    178. 	return num;
    179. }
    180.  
    181. int main() {
    182. 	while(scanf("%d %d %d", &n, &w, &h) == 3) {
    183. 		if(w * h < n) {
    184. 			printf("0\n");
    185. 			continue;
    186. 		}
    187. 		if(w * h == n || n == 1) {
    188. 			printf("1\n");
    189. 			continue;
    190. 		}
    191. 		if(n == 10) {
    192. 			printf("%d\n", tenTable[(w-1)*10 + h-1]);
    193. 			continue;
    194. 		}
    195. 		printf("%d\n", compute());
    196. 	}
    197. 	return 0;
    198. }

  • 相关阅读:
    【入门篇】ClickHouse 数据类型
    【iOS 第一周总结】-网易云的总结
    后端程序员生产力工具合集
    临时公式编辑
    算法与数据结构（2）--- 绪论（下）
    leetcode-1438： 绝对差不超过限制的最长连续子数组
    基础算法--二分查找
    python socket编程2 - socket创建发送方所需参数的获得
    ChatGPT终于接上视觉能力！
    了解 NFT 质押：Web3 中赚取被动收益的另一种方式
  • 原文地址：https://blog.csdn.net/qq278672818/article/details/133587400