UVa 12573六方向N步计数：从BFS打表到O(1)公式

前阵子刷 UVa 12573 Sohel Sir‘s Assignment，这道题让我在同一个坑里摔了两次：第一次老老实实写 BFS，小数据全对，数据一大直接超时；第二次推完公式兴冲冲交上去，又因为漏掉 N=1 的特判被 WA 到怀疑人生。题目描述很短，但里面藏了三个容易忽略的细节。这篇文章把完整思路、公式推导和踩坑记录都整理出来，给同样在做 UVa 或者刷组合计数题的朋友做个参考。

1. 题目到底在问什么：六个方向、恰好 N 步、去重计数

1.1 题意拆解

题目的大意是：在平面直角坐标系中，从原点出发，每一步可以选择六个方向之一移动一个单位，问走恰好 N 步之后，能够到达多少个不同的格子点。

听起来很简单，但你先别急着写 BFS。这里有三个关键词会决定你最终答案对不对。

第一个是“六个方向”。普通网格题是上下左右四个方向，这道题多了两个对角方向，也就是我们可以走：

• 水平两个方向：(1, 0)、(-1, 0)
• 垂直两个方向：(0, 1)、(0, -1)
• 两条对角线方向：(1, -1)、(-1, 1)

注意对角线不是 (1, 1) 这种，而是斜着穿过方格的对角步。把六个方向画在坐标系里，刚好是正六边形的六个顶点方向。也就是说，这个网格实质上是一个三角格点图，不是普通的方形网格。这一点理解错了，后面推公式会全部跑偏。

第二个关键词是“恰好 N 步”。不是“最多 N 步”，而是路径长度必须精确等于 N。多绕路可以，少走不行。也就是说，哪怕某个点距离原点只有 1 步，只要你能用 N 步走到它，它也要被计入答案。这一点直接导致了 N=1 时会出现一个非常反直觉的特例，后面我会专门讲。

第三个关键词是“不同的格子点”。同一个点完全可能被多条路径走到，比如先向右再向左就回到原点，但统计答案时只算一次。所以不能用简单的路径计数去套，要做的是集合大小的统计。

这道题在 UVa 里属于较新的题目，数据范围我记得可以给到很大，所以暴力搜索一定不是正解。你需要找到答案的数学规律，把 O(6^N) 的爆炸搜索压缩成 O(1) 的公式输出。

1.2 为什么不能直接 DFS

很多同学看到“六个方向、N 步、有多少个点”的第一反应就是 DFS 或 BFS。我一开始也是这么干的：用一个 set 存当前所有可达点，每一层把每个点往六个方向扩展一遍，最后数 set 里的点数。

这种思路在小数据下完全没问题。N=1 答案是 6，N=2 答案是 19，N=3 答案是 37，轻轻松松。但只要 N 到 20 左右，你可以自己去试一下：每一层能到达的点数按二次方增长，虽然比 6^N 小得多，但 set 操作加上逐层扩展，时间还扛得住；可一旦 N 到 100、1000，甚至 10^9，暴力就直接死掉了。

更要命的是 UVa 这类在线判题系统一般会给你多组测试数据。如果每组都要重新 BFS，那就算 N 只有几百，累积起来也会超时。所以这道题真正考的是推导能力：先在小范围打表找规律，再想办法证明规律，最后用公式输出。

1.3 方向集合的坐标写法

为了方便讨论，先把六个方向写成六组向量：

这六个向量在二维平面上形成一个闭合的对称结构。注意 (1, -1) 和 (-1, 1) 互为相反向量，另外两组也是。所以本质上，你手里相当于握住了三个轴方向的“正负步”，只是这三个轴不是互相垂直的，但组合起来同样能张成整个平面。

观察六个方向可以发现一个关键事实：沿某个方向走一步，再去掉沿另一个方向走一步，可能等效于某个单步方向。比如先 (0,1) 再 (1,-1)，合计是 (1,0)，也就是向右一步。这意味着同一个终点会有非常多的路径表示，所以去重是必须的，也正因为这种冗余，才让“恰好 N 步”变得大多数情况下都能实现。

2. 先别急着推公式：打表把规律“看”出来

2.1 用 BFS 打小数据的表

我不建议一上来就闷头推导，因为在没有结论的时候，你根本不知道要证什么。正确做法是先用暴力程序把 N=0 到 N=8 的答案全部算出来，盯着数字看几分钟。

打表代码非常简单。用 set 存点，用坐标结构体判重。我写了一个 C++ 版本的 BFS：

#include <bits/stdc++.h> using namespace std; struct Point { int x, y; bool operator<(const Point& other) const { if (x != other.x) return x < other.x; return y < other.y; } }; int main() { int dx[6] = {1, -1, 0, 0, 1, -1}; int dy[6] = {0, 0, 1, -1, -1, 1}; for (int N = 0; N <= 8; N++) { set<Point> cur, nxt; cur.insert({0, 0}); for (int step = 0; step < N; step++) { nxt.clear(); for (auto p : cur) { for (int k = 0; k < 6; k++) { nxt.insert({p.x + dx[k], p.y + dy[k]}); } } cur = nxt; } cout << "N = " << N << " -> " << cur.size() << "\n"; } return 0; }

这里每循环一次 step 就相当于走了一步，cur 里存的是当前步数下所有可达点。因为 set 会自动去重，所以最后 cur.size() 就是答案。我跑出来的结果如下。

2.2 观察到的序列

看到 1、6、19、37、61、91、127 之后，我第一反应是查差分。

• 6 - 1 = 5
• 19 - 6 = 13
• 37 - 19 = 18
• 61 - 37 = 24
• 91 - 61 = 30
• 127 - 91 = 36

从 N=2 开始，差分是 18、24、30、36，每次增加 6。也就是说，从 N=2 往后，相邻两项之差是 6(N+1)，或者说约等于 6 的倍数递增。二次差分恒定是 6，这强烈暗示答案是一个关于 N 的二次函数。

再对比一个经典数列：中心六边形数 1, 7, 19, 37, 61, 91, 127。除了 N=1 那一项差了 1，后面的 19、37、61、91、127 完全对上了。中心六边形数的通项是 1 + 3N(N+1)，也就是 3N^2 + 3N + 1。

打表结果已经给了很明显的信息：这道题的答案大概率就是 3N^2 + 3N + 1，只不过当 N=1 时需要特殊处理，因为数列里 1 对应的不是 7，而是 6。

2.3 差分和公式如何对应

如果你手边有计算器，把 3N^2 + 3N + 1 验证一下：

• N=2：12 + 6 + 1 = 19
• N=3：27 + 9 + 1 = 37
• N=4：48 + 12 + 1 = 61

而相邻两项差的公式是：

(3(N+1)^2 + 3(N+1) + 1) - (3N^2 + 3N + 1) = 6N + 6 = 6(N+1)

这正好解释了打表里 N=2 往后差分是 18、24、30、36 的规律。差分等于 6 的倍数，意味着图形上每一圈新增的格点数量是线性增加的，这跟“六边形按圈向外扩展”的直觉完全吻合。

打表找规律的套路在这道题上体现得淋漓尽致：你不需要一开始就知道什么高深理论，只需要把前几项算出来，然后观察差分、二阶差分或者和已知数列比对。一旦发现二次差分恒定，就可以放心大胆地假设通项是二次函数。

3. 为什么答案是中心六边形数：几何解释与证明思路

3.1 三角格点与六边形圈

如果你把六个方向画成一个图，会发现所有可达点在平面上排布成一个六边形形状的网格，这正是三角格点图。从原点出发，走 0 步是圆心 1 个点；走 1 步以内能到的点，是围绕圆心的一圈 6 个点；走 2 步以内能到的点，又向外扩展一圈，新增 12 个点；走 3 步以内能到的点，新增 18 个点。

这里有一个关键观察：每一步最多让“到原点的某种距离”增加 1，而这个距离在三角格点上刚好可以用“六边形圈数”来衡量。走 N 步以内能到达的所有点，恰好是以原点为中心、半径为 N 的六边形内部及边界的全部格点。

那么，这个六边形内到底有多少个点？很简单，一圈一圈数：

• 第 0 圈（圆心）：1 个点
• 第 1 圈：6 个点
• 第 2 圈：12 个点
• 第 3 圈：18 个点
• ...
• 第 k 圈：6k 个点

所以走 N 步以内能到达的格点总数是：

1 + 6 + 12 + 18 + ... + 6N = 1 + 6 * (1 + 2 + ... + N) = 1 + 3N(N+1)

展开就是 3N^2 + 3N + 1。

你可能已经发现了，这个式子还有一个非常漂亮的等价形式：

3N^2 + 3N + 1 = (N+1)^3 - N^3

它就是相邻两个立方数的差。这不是巧合，而是中心六边形数和立方数之间的经典关系。所以在代码里，你既可以写 3LL * N * N + 3LL * N + 1，也可以写 (N+1)^3 - N^3。就编程而言，前者更直接，不会因为乘方溢出出问题。

3.2 为什么 N>=2 时“恰好 N 步”能覆盖全部点

上面数的是“N 步以内”能到达的点，但题目问的是“恰好 N 步”能到达的点。这里需要论证一件事：对任意一个距离原点不超过 N 的格点，都一定存在一条长度恰好为 N 的路径走到它。

先看原点本身。N=2 时，可以先走 (1,0) 再走 (-1,0) 回原点；N=3 时，可以走 (1,0)、(-1,1)、(0,-1)，三个向量加起来是 (0,0)。所以只要 N>=2，原点都能被恰好走到。

再看距离原点 1 步的那些点，比如 (1,0)。N=2 时，可以走 (0,1) + (1,-1)，合计就是 (1,0)；N=3 时也能走，因为可以先用两步到达 (1,0)，再绕一个三角形环回到原位。所以距离 1 的点在 N>=2 时也都能被恰好走到。

那么距离更远的点呢？假设某个点最短需要 L 步到达，其中 L<=N。你需要把步数从 L 补到 N。怎么补？有两个基本“绕路”手段：

• 两步往返：走一个方向再走它的反方向，合计 2 步，位置不变，比如 (1,0) + (-1,0)。
• 三步三角环：走三条方向向量合计为 0，3 步回到原点，比如 (1,0) + (-1,1) + (0,-1)。

由于 2 和 3 可以组合出任何不小于 2 的整数差值（除了 1），所以只要 N-L 不等于 1，补步数都能实现。唯一需要担心的是 N-L=1 的情况，也就是路径长度只比最短距离多 1。这时候因为 3 步三角环和 2 步往返都加不进去，看起来会出问题。但实际分析会发现，对于 L>=1 的任意点，都可以直接用一条长度为 L+1 的折线走到它，因为三角形的存在让“走一步之后再绕个小弯”变得非常容易。所以真正无法处理的情况只有 L=0 且 N=1，也就是原点只用一步回不去。

因此结论就是：N=0 时答案是 1，N=1 时答案是 6，N>=2 时答案等于中心六边形数 3N^2 + 3N + 1。

这是一个很典型的“先数后证”路径：先用几何直观告诉你总点数是多少，再用三角格点上的绕路性质说明这些点都能被刚好覆盖到。日常做题时，你不需要把证明写得像论文那么严格，但至少要能说服自己。

3.3 N=1 这个特例是怎么来的

为什么打表结果里 N=1 是 6，而不是公式给的 7？因为公式 1+3N(N+1) 算的是“距离原点不超过 N 的所有格点”，其中包含原点。当 N=1 时，这个集合是原点加周围 6 个点，共 7 个。但“恰好 1 步”从原点出发不可能留在原点，一步走出去位置就变了，所以原点必须从答案中去掉，剩下 6 个。

这个特例极其阴险。你从 N=2 开始推规律，得到 3N^2+3N+1，验证 N=2、3、4 全对，想当然地认为 N=1 也适用，结果提交上去 WA。标准的 UVa 题解里基本都有一行 if (n == 1) 的特判，原因就在这里。

如果你的代码还能遇到 N=0 的输入，那就更要注意：公式在 N=0 时算出来是 1，而 0 步只能待在原点，答案恰好是 1，所以 N=0 用公式也正确。但很多题目给的约束是 N>=1，这时候 N=1 特判就足够了。

4. 代码实现与边界处理

4.1 C++ 主代码

当你确定了公式和特判之后，AC 代码非常短。这里我给出一个标准的 EOF 写法：

#include <cstdio> int main() { long long n; while (scanf("%lld", &n) == 1) { if (n == 1) { printf("6\n"); } else { printf("%lld\n", 3LL * n * n + 3LL * n + 1); } } return 0; }

有几个点需要解释一下。

第一，为什么要用 long long？因为 3N^2 这一项在 N 比较大时增长很快。假设 N 可以到 10^9，那么 N^2 是 10^18 级别，int 只有 32 位，最大能表示约 2.1×10^9，远远不够。long long 在绝大多数在线判题系统里是 64 位，能扛住这个范围。我一开始用 int 交，小数据没问题，一旦题目里有大 N 的测试点就爆掉，所以直接上 long long 是最稳妥的。

第二，为什么用 while (scanf("%lld", &n) == 1)？因为 UVa 老题的风格一般是不给测试组数，而是不断读入直到文件结束。如果你只读一组数据，遇到多组输入就会漏算。有的题目第一行会先给 T，那就改成先读 T 再循环 T 次，但原题我记得是非 EOF 莫属，所以采用这个写法。

第三，特判 n == 1 一定要放在公式之前。因为 n=1 时代入公式得到 7，答案是 6，差的是原点。如果题目给的 N 可能是 0，你要不要特判？不需要，因为公式在 N=0 时算出的结果是 1，和实际一致。

4.2 Python 的实现与快速验证

如果你平时用 Python 刷题，或者想迅速验证小数据，代码更简洁：

import sys for line in sys.stdin: line = line.strip() if not line: continue n = int(line) if n == 1: print(6) else: print(3 * n * n + 3 * n + 1)

Python 的整数没有溢出问题，所以直接算就行。但要注意输入里可能混有空行，所以 strip 之后跳过空行是个好习惯。

我还建议你把 BFS 打表代码和这段公式代码放在一起，写一个对拍程序。随便生成几个小 N，对比 BFS 结果和公式结果，一旦发现不一致立刻定位。这种对拍习惯在算法竞赛里非常有用，能够避免你把一个错误的规律当成真理直接提交。

4.3 时间复杂度与空间复杂度

公式解的时间复杂度是每组数据 O(1)，空间复杂度是 O(1)。不管 N 有多大，不管有多少组数据，每个测试点都是常数时间。相比 BFS 的状态爆量，这完全是降维打击。

在线判题最讨厌的就是超时和超内存。超时可以通过推公式解决，超内存则直接不会出现在这道题里。你只需要小心输入输出别太慢。C++ 里如果用了 cin/cout，建议加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)，或者干脆用 scanf/printf，这样在大数据量下会稳很多。

5. 常见问题与排查技巧实录

5.1 WA 的经典原因汇总

我在群里见过好几个同学卡在这道题，总结下来基本就是下面几个原因。

第一个就是漏掉 N=1 特判。这也是最常见的错误。如果你提交后 WA，但你已经推导出公式，优先检查是不是这个问题。直接把 n==1 特判加上，十有八九就过了。

第二个是 int 溢出。很多同学看完题意觉得 N 最大可能也就几万，直接用 int 写，结果题目隐藏数据里冒出个大 N，WA 或者报运行时错误。建议所有涉及平方的中间结果一律用 long long。

第三个是读入方式不对。题目如果有多组数据，你却只用 scanf 读了一次，那程序只会处理第一个测试点，后面的全部忽略，自然 WA。处理 EOF 是 UVa 的老传统，养成 while (scanf(...) == 1) 的习惯能帮你少踩很多坑。

第四个是方向集合写错。虽然你没有用 BFS 做最终代码，但如果打表阶段方向就写错了，你观察到的规律就是错的。六个方向里最容易漏的是 (1,-1) 和 (-1,1) 这对对角线，或者误写成 (1,1)。一旦方向错，打表数据就和正确题意不符，后续推导全废。

我整理成表格方便你对照排查：

5.2 怎么快速自检公式

给你一个笨但有效的方法：写一个 15 行的暴力程序，把 N=0 到 N=7 的答案全算出来，然后写一个公式程序输出同样范围的答案，两个程序的结果并排打印，肉眼比对。

我用的方向数组是这样的：

int dx[6] = {1, -1, 0, 0, 1, -1}; int dy[6] = {0, 0, 1, -1, -1, 1};

注意这里的方向顺序无所谓，只要六个方向齐全就行。我的顺序是右、左、上、下、右下、左上。你根据自己的习惯调整即可。

对拍时重点看 N=1：暴力输出 6，公式输出 7，这时候你就知道特判必须加。其他 N 值两边应该完全一致。如果 N=2 或 N=3 就对不上，那多半是方向写错，或者公式算错。

5.3 从这道题延伸出去的套路

“打表找规律 -> 差分判断 -> 假设通项公式 -> 特判边界 -> O(1) 输出”这个流程，在组合计数题里非常通用。UVa 和同类在线判题里有一批题都是这个套路，核心就是让你从小数据里发现二次或线性规律。

比如很多六边形棋盘、三角形网格计数题，答案最后都是 3N^2+3N+1 这种形式。你甚至可以记住一个规律：如果差分序列是等差数列，原数列就是二次函数；如果二阶差分恒定，通项一定是二次多项式。反过来，如果差分序列是等比数列，那就要往指数函数上想。

另外，(N+1)^3 - N^3 这个形式值得单独记一下。它既可以是中心六边形数，也对应着三维空间里立方体的增长量。在解题时如果发现答案和立方差有关，大概率能找到几何解释。

我个人做这道题的体会是：不要轻视任何一道“看起来像搜索”的题。你花五分钟写个 BFS 打表，可能帮你省下五个小时的无效推导；而推公式的时候，也一定要记得把 N 的每个小值都代入验证一遍，尤其是 0 和 1，因为边界永远是最容易出错的地方。以后遇到类似题目，先暴力拿小数据，再盯着数字多看一眼，答案往往就自己跳出来了。