题源链接洛谷 P14358 [CSP-J 2025] 座位 / seat一、背景在算法竞赛的模拟专题中有一类问题特别考验选手的细心——它们不涉及复杂的算法但要求你对规则的理解毫厘不差。CSP-J 2025 的这道座位题就是这类问题的典型代表。题目场景很真实考场座位按成绩从高到低蛇形排列。成绩最高的坐第 1 列第 1 行第二高的坐第 1 列第 2 行……第n nn高的坐第 1 列第n nn行第n 1 n1n1高的坐第 2 列第n nn行第n 2 n2n2高的坐第 2 列第n − 1 n-1n−1行……以此类推形成一条蛇形路径。初看之下这道题似乎只是排序 填矩阵但魔鬼藏在细节里——列优先还是行优先奇数列向下还是向上边界怎么转向本文就从这道座位题出发聊聊蛇形矩阵的填充规律以及模拟这个最朴素却最可靠的策略。二、核心思想2.1 蛇形填充从规则到代码拿到这道题很多选手可能会先画一个矩阵手动走一遍填充过程。这是非常好的直觉——蛇形矩阵的问题画图理解比空想高效得多。以n 4 , m 5 n 4, m 5n4,m5为例蛇形填充的路径如下列 1 列 2 列 3 列 4 列 5 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 1 │ → │ 8 │ ← │ 9 │ → │16 │ ← │17 │ 行 1 └───┘ └───┘ └───┘ └───┘ └───┘ ↓ ↑ ↓ ↑ ↓ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 2 │ → │ 7 │ ← │10 │ → │15 │ ← │18 │ 行 2 └───┘ └───┘ └───┘ └───┘ └───┘ ↓ ↑ ↓ ↑ ↓ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 3 │ → │ 6 │ ← │11 │ → │14 │ ← │19 │ 行 3 └───┘ └───┘ └───┘ └───┘ └───┘ ↓ ↑ ↓ ↑ ↓ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 4 │ → │ 5 │ ← │12 │ → │13 │ ← │20 │ 行 4 └───┘ └───┘ └───┘ └───┘ └───┘规律一目了然奇数列1, 3, 5…从上到下填充行号递增偶数列2, 4, 6…从下到上填充行号递减边界转向每列填满后向右移动到下一列蛇形填充的特征列优先与常见的行优先遍历不同本题按列填充方向交替奇偶列方向相反形成蛇形效果边界触发转向到达行边界时自动换列2.2 为什么直接模拟就够了这道题的数据范围很小n , m ≤ 10 n, m \leq 10n,m≤10左右n × m ≤ 100 n \times m \leq 100n×m≤100。这意味着排序O ( n × m × log ⁡ ( n × m ) ) O(n \times m \times \log(n \times m))O(n×m×log(n×m))完全够用模拟填充O ( n × m ) O(n \times m)O(n×m)更是微不足道不需要任何数学公式推导位置直接走一遍就行我们可以把这道题想象成走迷宫迷宫是一个n nn行m mm列的网格你的行走规则是奇数列往下走偶数列往上走走到头就右转进入下一列每走一步就在脚下放一个成绩牌找到小 R 的成绩牌报告位置这种直接模拟的策略在竞赛中非常常见尤其是当数据范围小、规则明确时。它的优势是直观、不易出错、调试友好。2.3 排序确定填充顺序题目说成绩互不相同且按从高到低填充。这意味着我们需要把所有成绩降序排序按排序后的顺序依次放入蛇形矩阵找到小 R 的成绩输入的第一个数在排序后的位置根据该位置在蛇形填充过程中确定行列坐标排序的作用就像排队先把所有人按成绩排好队然后按顺序一个个安排座位。三、算法模板3.1 算法到底在干什么——直觉解释我们的算法是一台自动排座机收集信息读入所有考生的成绩记住目标把小 R 的成绩记下来输入的第一个数排序排队把所有成绩从高到低排好蛇形入座按蛇形规则一个一个安排座位找到小 R当安排到小 R 的成绩时输出他的座位整个过程就像机场值机旅客按会员等级排好队排序然后按顺序一个个到柜台办理蛇形填充找到你的登机牌时就知道座位号了。3.2 万能模板 —— 伪代码 实战代码伪代码function 蛇形排座(n, m, 成绩[1..n*m]): target 成绩[1] // 小 R 的成绩 sort(成绩, 降序) r 1, c 1 // 从第 1 列第 1 行开始 for i 1 to n*m: matrix[r][c] 成绩[i] if 成绩[i] target: return (c, r) // 输出列行 // 蛇形移动 if c 为奇数 且 r n: c 1 // 奇数列到底右移 else if c 为偶数 且 r 1: c 1 // 偶数列到顶右移 else if c 为奇数: r 1 // 奇数列向下 else: r - 1 // 偶数列向上实战代码通用模板#includebits/stdc.husingnamespacestd;intn,m;inta[105];intb[15][15];intk;boolcmp(intx,inty){returnxy;}intmain(){cinnm;for(inti1;in*m;i)cina[i];ka[1];sort(a1,a1n*m,cmp);intr1,c1;for(inti1;in*m;i){b[r][c]a[i];if(a[i]k){coutc rendl;return0;}if(c%2rn)c;elseif(c%20r1)c;elseif(c%2)r;elser--;}return0;}3.3 例题实现 —— 本题完整代码#includebits/stdc.husingnamespacestd;// 蛇形填充规则// 1. 如果列数为奇数行数为n则列1// 2. 如果列数为偶数行数为1则列1// 3. 如果列数为奇数行1// 4. 如果列数为偶数行-1intn,m;// n:行数, m:列数inta[105];// 存储所有输入的数字intb[15][15];// 蛇形填充后的矩阵intk;// 要查找的目标数字// 比较函数降序排序boolcmp(intx,inty){returnxy;}intmain(){// 输入行数和列数cinnm;// 输入所有数字for(inti1;in*m;i){cina[i];}// 记录第一个数字作为目标值ka[1];// 对所有数字进行降序排序sort(a1,a1n*m,cmp);// 初始化当前位置从左上角开始intr1,c1;// r:行, c:列// 蛇形填充矩阵并查找目标数字的位置for(inti1;in*m;i){// 将当前数字放入矩阵b[r][c]a[i];// 如果找到目标数字输出其位置列行if(a[i]k){coutc rendl;return0;}// 根据蛇形填充规则移动到下一个位置// 情况1当前列为奇数且到达最后一行向右移动到下一列if(c%2rn){c;}// 情况2当前列为偶数且到达第一行向右移动到下一列elseif(c%20r1){c;}// 情况3当前列为奇数向下移动一行elseif(c%2){r;}// 情况4当前列为偶数向上移动一行else{r--;}}return0;}3.4 对比实现 —— 直接模拟 vs 数学公式对于蛇形矩阵如果数据范围很大可以用数学公式直接计算位置避免模拟方案核心思想时间复杂度适用场景直接模拟本题做法按规则一步步走O ( n × m ) O(n \times m)O(n×m)数据范围小最直观数学公式根据排名直接算行列O ( 1 ) O(1)O(1)数据范围极大需要快速查询预处理映射先建好排名到位置的映射表O ( n × m ) O(n \times m)O(n×m)预处理多次查询不同排名的位置数学公式的推导思路设小 R 的排名为r a n k rankrank1 11到n × m n \times mn×m列号c ⌈ r a n k / n ⌉ c \lceil rank / n \rceilc⌈rank/n⌉如果c cc为奇数行号r ( r a n k − 1 ) % n 1 r (rank - 1) \% n 1r(rank−1)%n1如果c cc为偶数行号r n − ( r a n k − 1 ) % n r n - (rank - 1) \% nrn−(rank−1)%n对于本题n × m ≤ 100 n \times m \leq 100n×m≤100直接模拟完全够用而且更不容易出错。3.5 变体清单 —— 常见变形变体类型题目描述关键变化解法调整行优先蛇形按行填充奇数行从左到右偶数行从右到左填充方向变化交换行列角色规则对称螺旋填充从外向内螺旋填充边界变化维护四个边界逐步收缩对角线填充按对角线方向填充路径变化按对角线枚举注意边界成绩相同处理成绩可能相同去重或稳定排序增加排名处理逻辑多次查询查询多个考生的座位查询次数多预处理映射表O ( 1 ) O(1)O(1)查询三维蛇形n × m × k n \times m \times kn×m×k的三维矩阵维度增加增加一维规则类似3.6 什么时候不能用——边界条件和反例直接模拟虽然简单但也有需要注意的边界成绩不唯一题目保证成绩互不相同如果成绩有重复排序后需要额外处理如稳定排序或记录原始下标。n 1 n 1n1或m 1 m 1m1单行或单列时蛇形退化为直线转向逻辑需要正确工作本题代码可以正确处理。输出格式题目要求输出列 行而非行 列顺序不能搞反。排序稳定性sort是不稳定排序但本题成绩互不相同不影响结果。数组越界确保矩阵数组大小足够b [ 15 ] [ 15 ] b[15][15]b[15][15]对于n , m ≤ 10 n, m \leq 10n,m≤10足够。四、底层逻辑4.1 为什么蛇形填充的规则是对的我们可以用数学归纳法证明填充规则的正确性。不变量在填充过程中当前位置( r , c ) (r, c)(r,c)始终是已填充区域的下一个合法位置。基础情况第1 11个成绩放在( 1 , 1 ) (1, 1)(1,1)显然合法。归纳步骤假设前i − 1 i-1i−1个成绩已正确填充。对于第i ii个成绩如果当前列c cc为奇数且r n r nrn向下移动r → r 1 r \to r1r→r1仍在同一列合法如果当前列c cc为奇数且r n r nrn向右移动c → c 1 c \to c1c→c1进入下一列合法如果当前列c cc为偶数且r 1 r 1r1向上移动r → r − 1 r \to r-1r→r−1仍在同一列合法如果当前列c cc为偶数且r 1 r 1r1向右移动c → c 1 c \to c1c→c1进入下一列合法每种情况都保证了新位置是未填充的且最终覆盖整个矩阵。因此规则正确。4.2 与经典问题的对比这道题和经典的矩阵填充问题家族有密切联系问题填充规则核心特征时间复杂度本题列优先蛇形奇数列向下偶数列向上列优先方向交替O ( n × m ) O(n \times m)O(n×m)行优先蛇形奇数行向右偶数行向左行优先方向交替O ( n × m ) O(n \times m)O(n×m)螺旋矩阵顺时针/逆时针螺旋边界收缩O ( n × m ) O(n \times m)O(n×m)对角线遍历按对角线方向对角线枚举O ( n × m ) O(n \times m)O(n×m)Z 字形遍历Z 字形路径特定模式O ( n × m ) O(n \times m)O(n×m)可以看到这些问题的共同特征是规则明确、路径确定、可以直接模拟。区别在于转向条件和移动方向不同。4.3 隐含约束的分析题目中有几个容易被忽略但至关重要的细节成绩互不相同保证了排序后每个成绩的位置唯一确定不会出现并列情况。a 1 a_1a1​是小 R 的成绩输入的第一个数就是目标需要在排序前记录下来。输出列 行而非行 列这是题目特意设计的陷阱很多选手会习惯性地输出行在前。蛇形是列优先与常见的行优先蛇形不同本题按列填充。如果按行填充结果会完全不同。五、决策表面对矩阵填充/遍历类问题如何根据规则快速选型场景特征推荐方案时间复杂度备注规则简单数据范围小直接模拟O ( n × m ) O(n \times m)O(n×m)本题场景最直观规则复杂多次查询预处理映射表O ( n × m ) O(n \times m)O(n×m)预处理查询O ( 1 ) O(1)O(1)数据范围极大数学公式O ( 1 ) O(1)O(1)需要推导位置公式路径不规则DFS/BFSO ( n × m ) O(n \times m)O(n×m)如迷宫遍历需要输出路径记录前驱O ( n × m ) O(n \times m)O(n×m)增加路径数组一句话总结规则简单直接走范围极大推公式多次查询建映射。六、工程视角蛇形矩阵和模拟填充的思想在实际工程中有着广泛的应用图像扫描与打印在图像处理中某些扫描仪和打印机采用蛇形扫描路径如行优先蛇形以减少打印头的移动距离。类似的数据存储也可以采用蛇形布局来优化缓存局部性。座位安排与资源分配在会议室、剧院、考场等场景中蛇形排列可以确保相邻座位的人能力/等级相近如本题或者确保通道两侧的人交替分布如某些考试防作弊布局。矩阵存储优化在某些数值计算中矩阵按蛇形顺序存储可以改善缓存命中率因为相邻访问的元素在内存中也相邻。这在图像处理和科学计算中有实际应用。游戏地图生成在某些游戏中地图的生成或遍历采用蛇形路径可以创造特定的视觉效果或游戏机制如贪吃蛇、某些解谜游戏的地图设计。七、小结本文从一道 CSP-J 真题出发探讨了蛇形矩阵与排序定位问题。核心认知可以总结为当问题的规则明确且数据范围小时直接模拟是最可靠的策略蛇形矩阵的核心在于方向交替和边界转向理解规则后代码实现非常简洁。用公式化的语言概括位置 ( r a n k ) { ( ⌈ r a n k n ⌉ , ( r a n k − 1 ) m o d n 1 ) , if ⌈ r a n k n ⌉ 为奇数 ( ⌈ r a n k n ⌉ , n − ( r a n k − 1 ) m o d n ) , if ⌈ r a n k n ⌉ 为偶数 \text{位置}(rank) \begin{cases} \left(\left\lceil\frac{rank}{n}\right\rceil, \ (rank-1) \bmod n 1\right), \text{if } \left\lceil\frac{rank}{n}\right\rceil \text{ 为奇数} \\ \left(\left\lceil\frac{rank}{n}\right\rceil, \ n - (rank-1) \bmod n\right), \text{if } \left\lceil\frac{rank}{n}\right\rceil \text{ 为偶数} \end{cases}位置(rank){(⌈nrank​⌉,(rank−1)modn1),(⌈nrank​⌉,n−(rank−1)modn),​if⌈nrank​⌉为奇数if⌈nrank​⌉为偶数​其中r a n k rankrank是成绩排序后的排名1 11到n × m n \times mn×m输出格式为列行。这道题教会我们的不仅是如何写排序和条件判断更是一种**“规则即代码”**的思维方式在算法竞赛中很多模拟问题的解法就是把题目描述的规则一行一行翻译成代码。蛇形矩阵的转向规则、边界条件都可以直接从题意中提取。这种读题即编程的能力是处理模拟类问题最核心的素养。如果这篇文章对你有帮助欢迎点赞收藏有任何问题欢迎在评论区留言交流。