如果你刷洛谷普及组题单大概率会在某个晚上撞见 P2239。名字叫螺旋矩阵看起来像一道“模拟填数”的签到题但实际上它当年在 NOIP 2014 普及组里占了第三题的位置坑了不少只会开二维数组的人。题目本身一句话能说完给你一个 n把 1 到 n^2 按顺时针螺旋填进 n 行 n 列的矩阵再问第 i 行第 j 列填的是哪个数。麻烦在于 n 最大能到 30000整个矩阵有 9 亿个格子你既开不下这么大的数组也不可能真的把格子挨个填完。所以这题真正考的是另一件事你能不能从螺旋结构里提炼出规律用很小的代价直接算出答案。这篇文章我就把这题的思路、公式推导、代码实现和踩坑记录完整拆一遍适合刚学递归、还没接触过数学规律题的选手也适合想复习“矩阵坐标映射”的老手。1. 题目到底在问什么一道让你“别真去填矩阵”的题1.1 原题浓缩与样例推演先看一个最小的完整例子n4 时螺旋矩阵长这样行/列列1列2列3列4行11234行21213145行31116156行410987样例输入是4 2 3答案应该是 14。为什么是 14从上到下看第 2 行第 3 列在矩阵里正好是 14。螺旋的填法是从外到内一圈一圈顺时针转最外圈先填 1 到 12然后进入内部 2×2 的方框继续填 13、14、15、16。这里已经能看出一个关键事实螺旋矩阵天然分成一层一层的方框每一层是一个完整的闭环。如果目标点在某层的边界上直接按边的顺序数就能数出来如果在内部就说明答案藏在更小的层里。这个观察是所有后续做法的出发点。再手推几个位置来加深感觉(1,1)显然是 1(4,1)是 10(3,3)是 15(3,4)是 6。你可以拿这些坐标去验证之后写出来的公式如果公式算出来的数和手推不一致那一定是边界处理出了问题而不是“矩阵不一样”。很多选手做这题最容易犯的错就是没把小矩阵的位置数清楚就急着写代码最后对着样例调试半天。1.2 数据范围给出的第一道门槛n≤30000 这个限制不是说开不下数组就算了我们算一笔账n30000 时n^2 900000000已经接近 10 亿。如果开一个int类型的二维数组需要约 3.6 GB 内存NOIP 赛场的评测环境根本不可能给你这么大的空间就算内存真的够模拟填数需要 n^2 次赋值9 亿次操作在 1 秒限制里也几乎不可能跑完。所以这题从一开始就堵死了“先填表再查表”的路线。题目真正想让你发现的是规律螺旋矩阵从外到内可以看作一组边长递减的方框每个方框上的数字是连续的区间。只要目标坐标落在某一圈上就能用这一圈的起点加上相对偏移量直接算出结果如果目标坐标不在当前圈上就把当前圈整体跳过把问题缩小到内层。这个“剥洋葱”的过程完全不需要生成整个矩阵时间复杂度只有 O(n)最坏也才一万多次循环。换句话说题目不是考你会不会写四重循环去填一个矩阵而是考你会不会跳出惯性思维找到坐标到数字的直接映射。2. 核心思路分层计数与“剥洋葱”模型2.1 为什么不能暴力模拟有人说 n 小的时候模拟很好写为什么不能直接模拟因为这道题设置的 n 上限就是故意不让模拟过的。一个 30000 阶矩阵有 9 亿个元素哪怕每次操作只需要一纳秒也要接近一秒实际常数再乘上几倍就是稳稳超时而且你根本不可能在竞赛环境里申请这么大连续内存。更重要的是螺旋填数存在非常强的层次规律完全可以只对目标点做判断。你要做的是把矩阵看成洋葱一层层剥掉外壳直到目标点出现在当前层的外圈上然后顺着这一圈的边把它数出来。这个思路看起来简单但为什么当年很多人被卡住因为大家习惯了“把答案算出来再取”的直接思维缺少“先定位再计算”的转换能力。实际上螺旋矩阵就是一维连续整数按照固定顺序铺到二维空间里只要顺序公式清楚逆推坐标毫无难度。打个比方你把 1 到 100 分成 10 行 10 列按顺序填表要查第 7 行第 8 列的数直接(7-1)*108就够了根本不需要把表填出来。螺旋矩阵只是把“按行顺序”换成了“按圈顺序”本质仍是一个坐标到序号的映射问题。2.2 每一层外圈的数字数量假设当前层的边长为 len这一圈有多少个数最直观的理解四条边各 len 个但四个角被相邻边重复计算了一次所以总数是 4len - 4。也可以拆着看上边 len 个右边除右上角外 len-1 个下边除右下角外 len-1 个左边除左下角、左上角外 len-2 个加起来正好 4len-4。这个数量很重要因为当目标点不在这一圈上时这一整圈的数字可以整体“跳过”直接累加到答案的基准量里。以 n4 为例最外层 len4数量是 4×4-412所以内层从 13 开始第二层 len2数量是 4×2-44对应 13、14、15、16。以 n1 为例len1数量是 0等一下4×1-40但实际 n1 只有一个格子。这里要注意当 len1 时这一圈只有一个格并不能用 4len-4 来描述边但它恰好落在上边分支里直接返回 offset1 即可所以算法里不会真的把它当“空圈”处理。这个特殊值在实现时不需要额外讨论但理解公式时要清楚它针对的是 len≥2 的普通层。2.3 坐标“卷”进内层边界判断与递归转移现在假设目标点在这一圈上我们用当前圈的起点偏移量 offset 表示这一圈第一个数字之前的数字数量。按螺旋顺序四条边分别是上边、右边、下边、左边。判断的顺序必须固定成“上、右、下、左”否则角点会算重或算漏。以 1 下标记坐标设当前圈边长 len目标坐标 (i,j)上边条件i 1答案offset j。因为上边从左到右依次是这一圈的第 1 个到第 len 个数。右边条件j len答案offset len i - 1。上边已经把 len 个数填完右边从第 2 行开始往下数走到第 i 行还要走 i-1 步。下边条件i len答案offset 3*len - 1 - j。这里需要仔细推导上边 len 个右边 len-1 个一共已经填掉 2len-1 个下边从右往左走最后一个被填掉的格子是右下角所以下边实际从第 len-1 列开始。目标列 j 在下边上的相对步数是len-1-j因此值是offset 2*len (len-1-j)化简得到offset 3*len - 1 - j。左边条件j 1答案offset 4*len - 2 - i。上、右、下三边总共填掉 3len-2 个数字左边从下往上走从第 len-1 行开始目标行 i 的相对步数是len-1-i所以值是offset 3*len - 1 (len-1-i)化简得到offset 4*len - 2 - i。如果四个条件都不满足说明目标点在更小的内层方框里。这时先把当前这层全部跳过offset 4*len - 4然后把矩阵缩小一圈len - 2同时目标点的坐标在新坐标系中也要向内收缩i--j--。重复这个过程直到击中某条边。之所以坐标要减 1是因为剥掉最外面一圈后原来的第 2 行变成了新矩阵的第 1 行原来的第 2 列变成了新矩阵的第 1 列。你可以拿 n4 的(2,3)验证它不在最外圈累加 offset12新边长 len2新坐标是(1,2)落在上边返回12214完美匹配。2.4 为什么这是普及组第三题考察抽象能力NOIP 2014 普及组第三题的定位并不算高难的是思维转弯。前两题多是模拟和简单枚举到这一题突然让你处理 9 亿的规模很多选手第一反应是“我不会要开 9 亿数组吧”。真正需要的能力是把二维填充抽象成一层一层的序列并掌握递归或迭代的边界思想。这也解释了为什么网上很多题解都在强调“分层”只要你能把“层”这个概念想清楚这道题就是送分题反之如果死磕模拟大概率只能过 n 很小的数据点。另外这题还隐含着对“边界情况”的考察。坐标刚好落在角点、边长减到 1、目标点在中心附近这些情况稍不注意就会错。能把这题的边界吃透后面遇到任何跟矩阵坐标变换有关的题目都会更有底气。所以我一直觉得这道题是一道很典型的“普及组风格”题不考高级数据结构不考复杂算法就考你能不能把一个看似繁琐的过程压缩成一个简洁的数学模型。3. 一步一步实现从伪代码到 AC 代码3.1 先写一个只在某一层判断的函数先把边界公式封装成一个纯函数输入当前边长 len、当前坐标 (i,j)、累加偏移量 offset返回当前位置上数字。这个函数只处理“当前点在这一圈边界上”的情况不是边界就返回一个特殊值方便调用方决定是否继续剥圆。伪代码如下// 返回在边界上的数字-1 表示不在边界 long long ask(int len, int i, int j, long long offset) { if (i 1) return offset j; if (j len) return offset len i - 1; if (i len) return offset 3LL * len - 1 - j; if (j 1) return offset 4LL * len - 2 - i; return -1; }注意第三个分支的3LL * len这里的LL只是提醒自己这是 long long 运算防止在极端 edge case 下整数溢出。为什么第三分支写3*len - 1 - j而不是3*len - j这就是前面推导的下边公式。很多人在这里会少算 1。验证 n4 时下边从左到右的格子是 10、9、8、7取(4,2)3*4-1-29正确如果写成3*4-210就错到了左边的第一个格子。所以边界公式一定要回到原始推导去理解不要靠死记硬背。3.2 迭代和递归怎么选把递归写成 while 循环更稳妥。因为最坏情况下要从最外层剥到中心循环次数是 n/2 级别n30000 时约 15000 次完全没问题。但如果你写成递归函数调用深度也可能到 15000 层某些评测环境下会爆栈。竞赛里见过不少因递归太深而 RE 的选手所以这道题建议直接用循环代码还更短。递归版本看着优雅但 C 默认栈空间有限当深度上万时风险很大用 while 则完全不存在这个问题而且题目本身并不需要回溯循环写起来也不复杂。我自己的习惯是优先写循环除非题目明确要求递归或者递归深度很小。这道题用循环还有一个好处——你可以很容易在循环里加打印输出观察每一步 n、i、j、offset 的变化这对调试边界问题非常有帮助。递归版本想打印中间状态还得传引用或者用外部变量反而多一层麻烦。3.3 完整可提交的 C 代码下面给出一个可以直接 AC 的版本#include bits/stdc.h using namespace std; long long solve(int n, int i, int j) { long long offset 0; while (true) { if (i 1) return offset j; if (j n) return offset n i - 1; if (i n) return offset 3LL * n - 1 - j; if (j 1) return offset 4LL * n - 2 - i; offset 4LL * n - 4; n - 2; i--; j--; } } int main() { int n, i, j; cin n i j; cout solve(n, i, j) \n; return 0; }这段代码可以直接提交。注意四个分支的顺序不能乱当 n1 时第一次进循环就命中i1直接返回 1不会进入后面的减法所以不用额外特判。当 n2 时四个分支也能正确覆盖四个格子不用担心角点重复。主函数里用int读入 n、i、j 就够了因为它们的范围不超 int输出用long long的流式输出即可。3.4 边界情况与数据类型再单独说两个容易忽略的细节。第一读入的 i、j 是从 1 开始计数的不要手贱减成 0 下标上面所有公式都基于 1 下标减了反而错。第二offset累加的只是完整外圈的数字个数最大值是 n^2n30000 时是 9 亿int 其实能存下但中间offset 4LL*n - 4如果用 int 也还行为了保险和养成良好的习惯统一用 long long。输出时也记得用流式输出不要printf(%d)传 long long否则大数会输出错误。还有一个很多人会忽略的点3LL*n - 1 - j和4LL*n - 2 - i中的j和i都是 int但它们和 long long 混合运算时会自动提升所以不会有问题。反过来如果你把3LL * n写成了3 * n当 n 是 int 时乘法结果可能先溢出再转 long long 也救不回来。虽然这道题 n 只有 300003*n90000不会溢出但养成用LL的习惯有助于应对更复杂的题。4. 现场踩坑与调试实录4.1 常见错误速查表我整理了几个高频错误基本覆盖了这题能踩的主要坑错误现象可能原因解决办法样例4 2 3输出 13 或 15偏移量没加或公式少 1回看推导用 4×4 矩阵逐步验证小数据对大数据错n 减 2 但 i、j 忘记同步减 1在循环里打印四个变量检查坐标收缩递归版本 RE递归深度上万导致爆栈改成 while 循环左下角(n,1)算错分支顺序不对让左边分支抢走了下边格子保证判断顺序是上、右、下、左输出很大的负数或随机值用printf(%d)输出 long long改用cout或printf(%lld)表格里第一条看起来简单但确实是最多人卡住的地方。公式错一两个字符结果就差很多尤其是3*len-1-j少一个-1就完全不对。第二条是我见过很多选手踩的他们写n - 2很顺但忘了i和j也要跟着减 1结果坐标在内层越界或者命中错误的分支。4.2 手算样例与对拍技巧我调这题时最直接的技巧是画一个 5×5 的矩阵。5×5 螺旋长这样行/列列1列2列3列4列5行112345行2161718196行3152425207行4142322218行5131211109随手挑几个位置(2,5)6(5,2)12(3,3)25。用代码跑一遍如果和手算一致说明公式基本正确。但手算只能覆盖几个点更稳妥的是写一个暴力模拟填表的程序对小 n比如 n≤10和快速算法一起跑用随机坐标比较结果。一旦发现不等立刻缩小到能手动调的 n把每次 while 里的 n、i、j、offset 都打印出来看是哪一步坐标转移出了问题。这种对拍习惯越早养成越好不光是这道题以后做任何规律题都能用。我这里给一个暴力生成小矩阵的思路开一个vectorvectorint按螺旋方向模拟填充然后查询坐标值。由于 n 很小完全不用考虑性能。再用若干组随机坐标去和solve的结果对比写一个简单的对拍脚本或直接在同一个程序里比较。你会发现边界公式在 n1 和 n2 时也要正确这两个特殊值最容易在暴力对拍中暴露问题。4.3 关于复杂度O(n) 已经足够别惦记 O(1)这题标准做法就是循环 n/2 次最坏 15000 次循环在 OI 赛制下连零头都算不上。有些人会想能不能直接 O(1) 算能但不必要。想 O(1) 只需要先求出目标点在第几层再用等差数列求和算出前面所有层的数字总量最后在所在层的四条边上套公式问题是公式比上面的 while 复杂得多而且多组询问时才有明显收益。单次询问老老实实剥洋葱代码短、不容易错。竞赛题追求的首先是稳定拿到分其次才是常数优化。不要为了炫技把代码写到没法调试。我见过有选手强行 O(1) 推导最后因为一个求和公式写错样例都过不了反而得不偿失。所以对这道题我强烈建议先用 while 版本拿满分如果你想进阶再在草稿纸上推多组询问的 O(1) 做法这样进退都从容。5. 从这题延伸出去的思维模型5.1 同类“矩阵坐标映射”题对比螺旋矩阵属于“二维坐标 ↔ 一维序号”的映射题这一类题在 OI 和面试里反复出现。比如蛇形填数、回字形打印矩阵、旋转图像、剑指 Offer 的顺时针打印矩阵本质都是同一套思维先定位第几层再确定在四条边上的哪一段最后通过边长算出序号。刷完这题之后再遇到类似题可以先问自己三个问题目标在哪一层这一层从哪个数字开始从层的起点到目标点需要走几步把这三个问题解决任何变体都能拆掉。如果你去看别的题解会发现很多人把这题叫做“找规律题”。其实它不只是找规律更是一种计算几何式的坐标变换。对坐标做边界判断、相对偏移、矩形收缩这套操作在很多图形算法里都很常见。所以不要只把这题当一道一次性 AC 的题目而是把它当成一个思维模板以后用到矩阵操作时能有意识地联想到“剥层”这个方法。5.2 如果题目改成多组询问怎么办虽然本题只询问一次但扩展一下也有意思。目标点 (i,j) 所在层数可以由它到四条边的最短距离决定t min(i, j, n-i1, n-j1)。第 t 层之前的层数字总量等于对lenn, n-2, ...连续求和4*len-4可以写成等差数列和这样就能在 O(1) 内算出 offset。再把坐标平移到第 t 层内的相对坐标套用上面的四个边界公式即可。如果你在准备进阶可以试着把这段逻辑写出来写不出来的话回到 while 版本它也够用了。这里给个提示前面若干层的总偏移量 外层数量之和。假设当前层边长为 len0之前剥掉的层数为 k-1那么所有剥掉的边长序列是 n, n-2, ..., n-2(k-2)每一层数量是 4 倍边长减 4这些是等差数列求和公式可以手推。真正写代码时要注意层数从外到内的边界尤其是目标点正好矩阵中心时怎么处理。不过这些都是延伸话题对原题不是必须。5.3 给新手的第二天再刷建议新手做完这题别急着收藏题解。建议第二天重新打开题目先不看代码自己纸笔推一遍 4×4、5×5 的边界公式然后尝试把题目改写成“给定数字 k求它所在行和列”也就是把映射反过来。逆映射比正映射更容易出错能完整做出来的话说明你对螺旋结构的理解已经到位了。如果时间充裕再用小 n 写一个暴力填表程序和快速算法对拍把每个边界位置都覆盖到。这一套流程走下来比连续刷三道新题都值。最后说点个人体会。我第一次做这题时公式里的3*len-1-j和4*len-2-i对了几遍都不对最后是老老实实在草稿纸上把 4×4 矩阵抄了一遍然后在每个分支旁边标注“覆盖哪些格子”才把边界搞顺。后来我养成了一个习惯遇到矩阵类的规律题先画小矩阵、标格子、数步数再写代码。这一步看起来浪费几分钟实际能帮你省下几十分钟的调试时间。螺旋矩阵这道题到现在仍然常被推荐给初学者不是因为它难而是因为它能逼着你摆脱“暴力填表”的思维惯性。把这个坑踩过去你后面看很多坐标变换题都会轻松很多。
