1. 从一道题看算法竞赛中的几何与规律最近在整理蓝桥杯的练习题翻到了ALGO-436这道题题目名字叫“正六边形”。乍一看这应该是一道纯粹的几何计算题可能涉及面积、边长、坐标计算之类的。但如果你真的这么想那可能就掉进思维定势的坑里了。在算法竞赛中尤其是像蓝桥杯这种级别的比赛题目名称往往只是一个引子真正的内核可能隐藏在“正六边形”这个几何外壳之下考察的是你的数学抽象、规律发现和编程实现能力。我刚开始接触这类题时也犯过迷糊总想着去推导正六边形的各种几何公式结果代码写得复杂还容易出错。后来做得多了才明白竞赛题里的“正六边形”很多时候并不是让你真的去画一个图形或者计算它的几何属性而是借用这个规整的、对称的结构来构造一个数学模型让你去求解某种序列、路径或者状态的数量。这有点像“挂羊头卖狗肉”题目披着几何的外衣内核却是一道标准的动态规划、递推或者数论题。所以当我们拿到“ALGO-436 算法训练 正六边形”这道题时首先要做的不是打开几何课本而是冷静下来仔细阅读题目描述虽然本次输入未提供但我们可以基于经验推演常见的出题模式。我们需要明确题目到底给了什么条件是给出了边长求面积还是给出了蜂窝状结构的坐标求最短路径亦或是像“正六边形填数”这类问题要求我们计算某种填充方式的总数不同的题意对应的解题思路和代码复杂度是天差地别的。接下来我就结合几种常见的“正六边形”类算法题拆解一下背后的核心思路和解题技巧。2. 场景一坐标变换与蜂窝网格遍历这是“正六边形”题目中最经典的一类。正六边形可以紧密排列形成蜂窝网格Hexagonal Grid。在这种网格中每个单元格六边形的邻居不是上下左右四个而是六个。处理这类问题的第一步就是定义一套好用的坐标系统。2.1 坐标系的选择立方坐标 vs 轴向坐标直接使用二维笛卡尔坐标x, y来表示六边形中心点会很麻烦因为偏移量不是整数计算距离和邻居都很复杂。因此我们通常采用两种更优雅的坐标系。第一种是立方坐标Cube Coordinates。想象我们把六边形网格嵌入到一个三维空间里但满足约束条件 x y z 0。每个六边形中心对应一个三维坐标 (x, y, z)但因为它满足和为0所以实际上只有两个自由度。在这个坐标系下六个方向的移动向量变得非常简单东 (E): (1, -1, 0)西 (W): (-1, 1, 0)东北 (NE): (1, 0, -1)西南 (SW): (-1, 0, 1)西北 (NW): (0, 1, -1)东南 (SE): (0, -1, 1)两个六边形之间的距离就是三维坐标的曼哈顿距离除以2即(|dx| |dy| |dz|) / 2。这种坐标系的优势是对称性极好方向运算和距离计算非常直观。第二种是轴向坐标Axial Coordinates。这是立方坐标的简化版我们只取其中的 q 和 r 两个轴通常对应立方坐标的 x 和 z。这样一个六边形就用 (q, r) 来表示。六个方向的移动向量变为东 (E): (1, 0)西 (W): (-1, 0)东北 (NE): (1, -1)西南 (SW): (-1, 1)西北 (NW): (0, -1)东南 (SE): (0, 1)轴向坐标更节省存储也更容易映射到二维数组。两种坐标系可以互相转换。在算法题中如果题目给出的就是类似“向东走a步向西北走b步”这样的指令使用轴向坐标来实现BFS广度优先搜索或DFS深度优先搜索会非常方便。注意在编程实现时务必提前定义好这六个方向的偏移量数组例如int dirs[6][2] {{1,0}, {-1,0}, {1,-1}, {-1,1}, {0,-1}, {0,1}};。这能避免在代码中硬编码方向导致混乱和错误。2.2 BFS/DFS的应用路径与连通块建立了坐标系这类问题的核心算法往往就是BFS或DFS。例如题目可能是“给定一个由‘.’和‘#’组成的正六边形蜂窝地图‘.’代表空地‘#’代表障碍物求从起点到终点的最短路径步数。” 或者 “求地图中所有连通空地区域的面积六边形格数。”解题步骤如下数据读入与存储如何存储蜂窝地图是个小挑战。有时题目会按行给出但每一行的起始位置可能是对齐的也可能是交错的。我们需要根据输入格式将每个六边形单元格映射到我们定义的 (q, r) 坐标上。一个常见的技巧是将奇数行或偶数行进行水平偏移半个单位来模拟交错的排列。队列与访问标记使用标准BFS队列。访问标记数组visited[q][r]的大小需要提前估算好根据题目给出的坐标范围来定义防止数组越界。邻居遍历对于当前出队的节点 (q, r)遍历上面定义的六个方向(dq, dr)计算邻居坐标(nq q dq, nr r dr)。条件判断检查邻居坐标是否合法在地图范围内、是否未被访问、以及是否是可通过的空地非障碍物。状态更新如果满足条件则更新邻居的步数dist[nq][nr] dist[q][r] 1标记已访问并将其加入队列。踩坑点最容易出错的地方就是坐标映射和方向数组的定义。一定要在纸上画一个小的蜂窝网格标上你自己的 (q, r) 坐标然后验证你定义的六个方向向量是否真的指向正确的邻居。另一个坑是BFS求最短路径时在将节点加入队列时就要标记为已访问而不是在出队时才标记否则可能导致同一个节点被重复加入队列虽然结果可能正确但会严重影响性能在数据量大时可能导致超时或内存超限。3. 场景二图形生成与规律打印另一类常见的“正六边形”题目是要求你按照特定规律打印出一个由字符构成的六边形图案。比如“根据输入的边长n打印一个由‘*’组成的空心正六边形”或者“打印一个数字填充的六边形螺旋矩阵”。这类题不涉及复杂的算法但极其考验对循环控制、边界条件和对称规律的把握能力。3.1 空心正六边形的打印逻辑我们以打印边长为n假设n表示每条边上的字符数的空心六边形为例。一个正六边形可以看作是由一个顶行、一个底行、以及中间向上和向下的两个梯形侧面组成的。核心规律分析顶行/底行顶行和底行是相同的。它们有前导空格然后是一串连续的字符。前导空格的数量是n - 1。字符的数量是n。中间上半部分从第2行到第n行这部分构成六边形的上半部分侧面。每一行由三部分组成左侧前导空格、一个字符、中间空格、一个字符。左侧前导空格数从n - 2开始每行递减1。中间的空格数是一个等差数列。对于第i行i从2到n中间空格数为2 * (i - 2) 1。这样两个字符之间的间隔会随着行数增加而增大。中间下半部分从第n1行到第2n-2行与上半部分对称。左侧前导空格数从1开始每行递增1。中间空格数则从最大值开始递减。代码实现要点先单独处理顶行。然后用一个循环处理上半部分第2行到第n行在循环体内计算并输出前导空格、第一个字符、中间空格、第二个字符。接着再用一个循环处理下半部分第n1行到第2n-2行逻辑与上半部分对称。最后单独处理底行。注意在竞赛中打印图案题一定要注意行末空格很多在线评测系统OJ会对比你的输出和标准输出的每一个字符包括行末的空格。如果你的代码在每行末尾多打了空格就会被判为“输出格式错误”。一个安全的做法是在构建每一行的字符串时只添加必要的字符和中间空格而不要添加行尾空格或者使用trim类函数处理后再输出。3.2 数字填充与螺旋矩阵如果题目是打印一个数字填充的六边形例如从1开始按某种顺序如蛇形、螺旋形填充难度就上了一个台阶。这需要你更精确地控制二维数组的索引变化。解题思路确定二维数组大小首先需要计算出这个正六边形需要占用多少行、多少列。对于一个边长为n的六边形总行数是2 * n - 1。总列数需要根据中间最宽的那一行来计算通常是n 2*(n-1)这里容易算错。更稳妥的方法是先确定一个足够大的二维数组然后只填充有效区域。坐标映射将蜂窝六边形的每个“格子”映射到这个二维数组的特定位置。这又回到了我们之前讨论的坐标问题。你需要定义一个函数将 (q, r) 坐标转换为数组的 (row, col)。确定填充顺序按照题目要求的顺序如从外向内螺旋生成一系列 (q, r) 坐标。这可能需要模拟一个“笔”在六边形边界上移动的过程移动规则比矩形螺旋复杂因为方向有六个。填充与输出按照生成的坐标顺序将递增的数字填入对应的数组位置。最后只输出数组中属于六边形有效区域的字符非有效区域输出空格。这类题目的代码调试会非常耗时。我的经验是先写一个辅助函数用于可视化输出你的二维数组可以用不同的字符表示未填充、已填充、边界等状态。这样能快速定位坐标计算错误的地方。4. 场景三组合数学与动态规划这是“正六边形”题目中最难也最有趣的一类。题目可能问“在一个边长为N的正六边形网格中从最左下角到最右上角只能向右东、向右上东北、向右下东南走有多少种不同的路径” 或者 “用三种颜色给正六边形蜂窝网格染色要求相邻格子颜色不同问有多少种方案”这类问题彻底脱离了几何计算完全是一个组合数学或动态规划模型。4.1 路径计数问题我们分析上面那个路径问题“从最左下角到最右上角方向限制为东(E)、东北(NE)、东南(SE)”。首先我们必须用轴向坐标来思考。假设起点是(0,0)终点是(Q, R)。由于只能朝东、东北、东南走这意味着每一步坐标q可以理解为水平方向至少增加0东南、东北方向而东方向则增加1。实际上东(E:1,0)使q1东北(NE:1,-1)使q1且r-1东南(SE:0,1)使q不变且r1。你会发现总步数并不是固定的因为向东和向东北都会增加q而向东南不增加q。我们需要走的总的“水平进度”是Q。设向东走了a步向东北走了b步向东南走了c步。则有a b Q 因为只有东和东北增加q-b c R 东北使r减1东南使r加1总步数 steps a b c。这是一个不定方程。路径数等价于在满足上述方程的(a, b, c)非负整数解的前提下计算多重集合{a个E, b个NE, c个SE}的排列数。这是一个经典的多重排列问题方案数为(steps)! / (a! * b! * c!)。但题目往往不会这么直接终点可能不是某个具体坐标而是“最右上角”这样一个概念。这时“最右上角”需要你根据六边形的形状来定义。对于一个边长为N的六边形其“最右上角”的坐标是什么你需要根据网格的划分方式来确定。确定了起点和终点的坐标(Q,R)后就可以用上述组合数学公式或者用动态规划来求解。动态规划解法定义dp[q][r]为从起点走到坐标(q,r)的路径数。状态转移方程为dp[q][r] dp[q-1][r] dp[q-1][r1] dp[q][r-1]这里假设移动方向是E、NE、SE。这个方程需要根据你的方向定义来调整。DP的边界条件是起点dp[0][0] 1。最后dp[Q][R]即为答案。DP的好处是能处理更复杂的约束比如某些格子不能经过。4.2 染色问题与状态压缩DP给蜂窝网格染色是另一个经典问题。由于六边形每个格子有6个邻居这比矩形的4邻居要复杂。对于小规模的网格比如边长N5我们可以用状态压缩动态规划状压DP来暴力枚举。思路如下定义状态因为六边形一行中的格子是交错的我们不能直接用一行的状态来简单表示。一个常见方法是“轮廓线DP”。我们按某种顺序比如从上到下从左到右的“之”字形遍历每一个六边形格子。状态dp[pos][state]表示当前处理到第pos个格子以及它前面若干个相邻格子的颜色组合state。确定状态表示关键是如何用state表示之前格子的颜色。对于六边形当前格子可能和它左边、左上、右上、上方的格子相邻取决于遍历顺序。因此state需要能编码这些相邻格子的颜色。如果颜色有C种那么每个格子需要log2(C)位来存储颜色。我们需要维护一个“轮廓线”记录当前行和上一行相关格子的颜色。状态转移遍历当前格子所有可能的颜色1到C检查是否与state中编码的相邻格子颜色冲突。如果不冲突则更新状态转移到下一个格子。初始化与结果起始状态在第一个格子之前所有“相邻格子”的颜色可以视为一个特殊值如0表示没有冲突。最终当pos遍历完所有格子后将所有状态的方案数加起来就是总染色数。状压DP的实现难度很高需要对位运算非常熟悉并且能准确抽象出“轮廓线”。对于更大的N这类问题通常需要借助矩阵快速幂或容斥原理等更高级的数学方法这已经超出了蓝桥杯ALGO训练题的一般范围。在竞赛中如果遇到这类题数据规模一定会暗示你该用什么方法。如果N很小10状压DP是可行的如果N很大比如10^9那一定是有数学公式或者需要矩阵快速幂优化递推。5. 实战推演面对未知题干的解题策略既然我们手头没有ALGO-436的具体题干那么作为一个准备竞赛的选手应该如何应对呢以下是我总结的通用解题策略不仅适用于本题也适用于任何算法竞赛题目。5.1 第一步彻底理解题意与数据范围这是最重要的一步却最容易被忽视。你需要仔细挖掘题目描述的每一个词。输入格式是输入一个整数n还是多组数据每组数据的结构是什么输出格式是输出一个数还是输出一个图案行末空格和换行符有什么要求数据范围n的最大值是多少这个范围直接决定了你能用什么算法。如果n 10你可以用暴力搜索或状压DP如果n 1000O(n^2)的动态规划可能可行如果n 10^5你可能需要O(n log n)的算法如果n 10^9那几乎肯定需要数学公式或O(log n)的快速幂算法。样例认真分析样例输入和输出。自己手动模拟一下样例确保你的理解与样例一致。如果连样例都过不了说明题意理解有误。5.2 第二步识别问题本质与建立模型根据输入输出和数据范围猜测题目属于哪一类。如果输入是一个整数n输出也是一个整数很可能是组合计数、路径问题或数列问题。思考它和斐波那契数列、卡特兰数、组合数等有没有关系。尝试手动计算n1,2,3,4时的结果看看能否找到递推规律。如果输入是n输出是图案那就是图形打印题。重点分析图形的对称性、每一行空格和字符数量的变化规律。如果输入是一个网格或坐标那就是网格遍历或搜索题。确定是BFS求最短路径还是DFS求连通块或者是DP求方案数。对于“正六边形”这个标题结合“算法训练”的难度标签我个人的经验判断是它更可能属于前两类要么是简单的规律打印考察循环控制要么是稍有难度的路径计数/数列计算考察递推或组合数学。不太可能涉及非常复杂的状压DP或矩阵快速幂。5.3 第三步从小规模数据入手寻找规律这是破解数列/计数类问题的金钥匙。假设题目是“计算边长为n的正六边形网格中有多少个不同的等边三角形”这只是一个假设的题意。你不要一上来就想公式。而是应该画图。画出n1, n2, n3的六边形网格。数数。在图上手动数出n1,2,3时符合条件的三角形个数。假设你数出来结果是a11, a25, a315。找关系。看看相邻两项之间有什么关系a2-a14, a3-a210。差值是4,10... 这看起来像是二次关系或者看看a_n / a_{n-1} 的比值。猜公式。根据有限的几项猜测通项公式。例如感觉a_n像是 n(n1)(2n1)/6 之类的组合数公式你可以用n1,2,3代入你猜的公式验证。验证与证明。如果猜到了公式尝试用数学归纳法或其他组合意义去证明它。在竞赛中如果时间紧迫有时“猜出公式”并通过所有样例就可以提交了但这有风险。更稳妥的方法是根据你发现的规律比如递推关系来编写DP程序。5.4 第四步编写代码与测试一旦确定了算法模型就着手编写代码。模块化将坐标转换、方向判断、打印一行图案等功能写成独立的函数使主逻辑清晰。边界检查特别是数组下标一定要在访问前检查是否越界。测试用你手算的小样例n1,2,3测试你的程序确保输出正确。然后构造一些边界情况测试比如n0如果允许的话、n取最大值。效率估算对于你写的代码根据数据范围估算一下时间复杂度和空间复杂度确保不会超时或超内存。5.5 第五步提交与调试如果提交后没有通过仔细阅读评测系统的反馈。编译错误检查语法、头文件、函数名拼写。答案错误重新审视你的算法逻辑。用更多的测试数据来验证。是否忽略了某种特殊情况递推的初始条件对吗组合数的计算溢出吗时间超限你的算法复杂度是否过高有没有优化的可能例如递归是否可以用迭代代替是否有重复计算可以用记忆化搜索或DP优化内存超限你的数组是否开得过大是否可以用滚动数组优化最后关于ALGO-436这道题虽然我们不知道具体内容但通过以上对“正六边形”类问题全面的拆解你应该已经掌握了应对它的所有武器。无论是图形打印、坐标搜索还是组合计数其核心思想都是将几何问题转化为有规律的数学模型或离散的算法问题。在竞赛中保持这种思维转换的灵活性比死记硬背某个特定题的解法要重要得多。我个人的习惯是在练习时即使做对了也会去网上搜一下这道题的题解看看别人有没有更巧妙、更简洁的思路不断积累不同的建模方法和编程技巧。