99年ACM/ICPC 的final有一道蜜蜂的坐标的问题，非常有意思，和队友们讨论了许久都没能解决。记得那天做练习是我和肖筹划着用计算几何的方法估算出结果，虽然做法很独特，但毕竟是估算的，最后没有能过。后来我找了份解题报告，看到了解这类问题神奇地使用笛卡儿坐标，着实让人兴奋啊。所以准备了一份模板、数道类似问题和将蜜蜂坐标放在扫雷游戏里的应用，来一个蜜蜂问题的大汇总。
模板放在SHU ACM群里，含有一些处理正六边形拼成的坐标系的方法。
首先，蜂巢是由许多个正六边行无缝拼接而成的，这是一个美丽而奇特的自然结构，如图（图中程序是在解一道题时写的辅助程序，我也放在群与大家分享）：
题外话，先来讨论下为什么六边形可以无缝的拼接出一个平面，那么七边、八边行不行？其实是一个简单的小学题： 正n边形内角为 (n-2)*180/n ，要保证可以无缝拼接，就是一个圆可以被整数个n边形内角拼接，即 360=k*(n-2)*180/n => 2n=k(n-2)，用这个公式就能算一下是否正n边形能像六边行一样拼出一个平面了。
起初在遇到这样独特的结构时可能无法想象如何将其保存起来，可能会想到是不是做一个带六条链结点的链图？这样做的结果将是一个极难维护的链图，光是想到插入操作就起鸡皮疙瘩。
有一个十分巧妙的方法来储存这个怪异的结构：用二维数组。用二维数组保存四个方向或八个方向的东西肯定是很简单的，其实对于这个六向的结构，我们可以取二维数组的八向中的六向。即东、南、西、北、东北、西南（其实只要注意对称，六向可以随便取），这样相对的坐标向每个方向移动的偏移量就是：
东 南 西 北 东北 西南
x 1 0 -1 0 1 -1
y 0 -1 0 1 1 -1
到底正确与否呢，其实是必然正确的，只是我们损失了两个角（东南、西北），不过不碍事。通过上面这个方法不仅是保存了六边形的怪结构，而且也给这种结构指明了一个坐标表示的方法，在解题中这个概念很重要。
PKU 1134：
与蜜蜂坐标没关系的题目，只是样子是六边行的。题目意思是给出三行，每行代表一个方向，然后可以按任意顺序把数字放在这个方向的任意一列中（以abcba的顺序分配到abc里）。归纳一下可以得到以下结论， 最大的得分就是三行分别乘以下面的系数：
行1： a * 8 + b * 6 + c * 5
行2： a * 7 + b * 7 + c * 5
行3： a * 7 + b * 7 + c * 5 。所以枚举一下就可以求出最大值了。
PKU 2265：
这是非常简单、易上手的题目，熟悉两种坐标系对于解决蜜蜂问题很有帮助，这两个坐标系也是蜜蜂最常用的坐标，转换的方法就是直接上模板。
PKU 1870：
是99年FINAL的题目，除了用模板里的构造点来构造一个六边形结点（带XY轴坐标）以外，模板里有求两点间最短距离的函数。
求最短距离要以一点为原点，即用一点减去另一点的XY坐标。然后对相对的那个点的两种情况做处理：xy同正同负时，距离是max(|x|,|y|)；否则距离为距离是|x-y|。简单得想象一下就知道了。
PKU 1792：
是1870的升级版，除了要求最短的距离外，还需要求两个点间有多少种路径可以用最短的距离。其实求可能的路径数可以归约为求组合数的问题：
上图为例，在x>0 y>0的区域，最短距离是max(|x|,|y|),图中某点的最短距离很明显是 |x|，然后如何求路径数呢？这样思考，为了能到达那个点，所有路径在两点之间准没错吧（出了两点间的区域就不能最短距离了）。那在最短路径为d的情况下，取d中的一点让它或上或下（只要保证还在两点间的那块区域），不就可以得到一条新的路径？这样，在d中取c个点（c为最大的可变的点，或称关节），就是总路径数。那么总的路径数就是combine(d,c)了。巧合的是c的值情况与最短路径的值情况正好相反，即xy同正同负时，c为|x-y|；否则c为max(|x|,|y|)。
模板里有个函数实现此功能，不过自己写写也很简单的吧。
PKU 3036：
哈，在1792有点类似，不过做法完全不一样的题。求的是从原点出发到达距离为n的地方再回来的路径数。其实知道用动态规划和前面讲的六个方向的坐标的话，这道题目是非常简单的。动规方程见下：
dp[i][x][y] i表示距离原点i步；xy是点的坐标。
dp[i][x][y]= dp[i-1][x+1][y] + dp[i-1][x-1][y] + dp[i-1][x][y+1] +dp[i-1][x][y-1] + dp[i-1][x-1][y-1] + dp[i-1][x+1][y+1]
上面的是比较简单的或基于六向的坐标系的，下面两道比较有意思，是对于此类坐标系的扩充：
PKU 1957：
那个辅助程序就是我为了做这道题目而写的，用法是先输入walk，然后按lrotate可左转（正规化过）。
题目的解法很容易想到的，就是先将走过的点放在一个set里，然后做旋转和正规化，直到两个set的元素都相等为止。
依照行走的路线构造点不是件难事，从原点出发。旋转是比较费神的，正规化的话其实就是找出一个最左最右的点作为参照点，所有点减掉它就行了。
旋转可以从两个角度考虑，一是考虑求出了点之后做旋转，二是考虑在将行走路线做旋转然后求点。如果从前种方向考虑的话，会很累，在简单的四向的坐标系中点相对于原点的转动可以通过乘以一个变换矩阵得到，而对于一个六向的坐标系，举个例子：
一个二维数组保存的七个点（O表示该位置无值，X表示该位置是一个六边形结点）：
O X X X X O
X X X ===========> X X X
X X O 乘以变换矩阵 O X X
很明显，旋转后的不是原来使用的六向的坐标表示方法了。当然，调整变换矩阵的话，相信还是有办法解决的，但这毕竟是个较麻烦的活儿。
那么从后者的方向来考虑的话，事情就简单了很多。见下图：
按行走路线进行转换的思想就是上图所表现的，显而易见了吧。代码实现也是相当的简单。即将把原来的a方向的操作改为b方向操作等等。
这样的话，先输入第一种走法，正规化一下。然后输入第二种，做七次旋转（包括不转的那种），每次正规化后再比对两个集合就行了。
PKU 1518：
看上去很吓人的题目，跟计算几何又有关系，而且坐标系又是要六向的表示。Take it easy，先来看看一个扫雷游戏吧：
在扫雷游戏中有这样一个问题，鼠标点击了之后要出发事件，事件的参数只有鼠标点击的点的坐标(x,y)。求鼠标点击的是哪块雷区，知道了哪块雷区才可以做相应操作嘛。
通过平面坐标求六边形的坐标的方法其实满多的，在这里介绍一个简单的方法：
首先，要判断点是否在六边形内，经常使用的是用叉乘判断点对于凸边形的每个顶点是左转还是右转可以做到。不过这里不需要这么做，因为六边行都是紧凑得在一起，而且都是正多边形，所以求一下点到每个多边形中心的距离，然后取最小值可以找到它所在的六边形了（如果正好在边上，随便取哪个都一样）。
为了优化一点，不用对每个六边形都求一下它的中心与目标点的距离。可以先从距离估算出目标点的大致位置，然后包括大致位置的六边形在内，相邻的六个六边形再确定出最终点所在的六边形。
估算的方法是简单的计算几何（d是六边形边长，td是sqrt(3)*d/2，p是目标点）：
x = (int) Math.round((p.x * 2 / (3 * d)));
y = (int) Math.round(((-p.y + x * td) / (2 * td)));
知道了六边行的坐标，接下来的事情就容易了。求两坐标间最短路径，然后路径乘以2*td。再将具体的两个点与六边形中心的距离相加。就是结果了，当然要注意在同一个六边形内的两点是直接计算两点距离。
链接：
Ray's Blog: http://raythking.blogspot.com/
SHU-ACM-Group: http://groups-beta.google.com/group/shu-acm-group
Mineray: https://mineray.dev.java.net/
No comments:
Post a Comment