UVa 10632 Pyramid

题目描述在一个经典的电脑游戏中一个生物在金字塔形状的格子上跳跃。金字塔共有nnn行第iii行有iii个格子。生物每次只能跳到其正上方或正下方的相邻格子不能跳出金字塔。当生物落在一个格子上时该格子的颜色会按照红色→\to→绿色→\to→蓝色→\to→红色的顺序循环改变。给定每个格子的初始颜色R、G、B需要找到一个不超过500050005000次跳跃的序列使得所有格子最终都变为蓝色。你可以选择金字塔中任意一个格子作为起点保证解总是存在第一次改变颜色的格子是跳跃后落地的格子。输入格式输入包含多组测试用例最多505050组。每组测试用例的第一行是一个整数nnn2≤n≤402 \le n \le 402≤n≤40表示金字塔的高度。接下来nnn行描述金字塔的初始配置每行由大写字母R、G、B组成代表该行从左到右的颜色。输入以n0n 0n0结束该行不处理。输出格式对于每组测试用例输出两行。第一行包含两个整数表示起始位置第一个整数为行号111表示最顶行第二个整数为该行的格子编号111表示最左。第二行是一个由字符7、9、1、3组成的字符串表示跳跃方向7向左上方跳跃9向右上方跳跃1向左下方跳跃3向右下方跳跃字符串长度不超过500050005000。任何合法的跳跃序列都会被接受。样例输入4 B RG BGR GBRB 2 R GB 0输出3 1 193919193919373737717191991919373737 2 1 919题目分析题目要求我们构造一个长度不超过500050005000的跳跃序列使得金字塔中所有格子最终都变成蓝色。每个格子的颜色状态只有333种红、绿、蓝且每次落地都会推动该格子颜色循环一步因此我们可以把“还需要几次落地才能变蓝”作为每个格子的需求值dr,c∈{0,1,2}d_{r,c} \in \{0,1,2\}dr,c​∈{0,1,2}。由于n≤40n \le 40n≤40总格子数最多只有40×412820\frac{40 \times 41}{2} 820240×41​820个而跳跃次数上限为500050005000这意味着我们可以采用一种系统性的构造方法而不是搜索最短路。关键在于找到一种能够“逐个消灭”格子需求的操作模式同时保证过程中不会将已经变蓝的格子再次弄乱。观察金字塔的几何结构除了顶部的第111行和第222行之外其余行都可以通过特定的模式操作在不破坏上方已处理格子的前提下将当前行的格子逐一变为蓝色。递归地自底向上处理即可。解题思路本题解采用自底向上、按列归约的递归构造。核心思想是将金字塔从底部到顶部逐行处理对于当前行的每一个格子利用其与“右上方”或“左上方”邻格的来回跳跃在不影响更上方格子的前提下将其变蓝。颜色与方向编码将颜色映射为整数R→0\to 0→0G→1\to 1→1B→2\to 2→2。目标颜色为222。用dr,c(2−color3) mod 3d_{r,c} (2 - \text{color} 3) \bmod 3dr,c​(2−color3)mod3表示格子还需要几次落地。每次落地的效果等价于dr,c←(dr,c−1) mod 3d_{r,c} \leftarrow (d_{r,c} - 1) \bmod 3dr,c​←(dr,c​−1)mod3。跳跃方向用数字字符表示7\texttt{7}7向左上方(r,c)→(r−1,c−1)(r,c) \to (r-1, c-1)(r,c)→(r−1,c−1)9\texttt{9}9向右上方(r,c)→(r−1,c)(r,c) \to (r-1, c)(r,c)→(r−1,c)1\texttt{1}1向左下方(r,c)→(r1,c)(r,c) \to (r1, c)(r,c)→(r1,c)3\texttt{3}3向右下方(r,c)→(r1,c1)(r,c) \to (r1, c1)(r,c)→(r1,c1)递归函数的定义递归函数dfs(r,c)\texttt{dfs}(r, c)dfs(r,c)的含义是当前位于格子(r,c)(r, c)(r,c)且保证(r,c)(r, c)(r,c)及其左下、右下区域尚未被处理。函数会通过一系列跳跃最终将(r,c)(r, c)(r,c)及它“右下方”的所有格子全部变为蓝色并且结束时的位置固定为(n,n)(n, n)(n,n)金字塔底部右下角或某个特定位置便于上层调用。递归分两种情况对角线格子(rc)(r c)(rc)此时(r,c)(r,c)(r,c)和其右下方邻居(r1,c1)(r1, c1)(r1,c1)构成一对。首先反复执行“右下→\to→左上”37\texttt{3} \texttt{7}37的组合第一步3\texttt{3}3跳到(r1,c1)(r1, c1)(r1,c1)落地将其需求减111第二步7\texttt{7}7跳回(r,c)(r, c)(r,c)落地将其需求减111。这样一次往返恰好让(r,c)(r,c)(r,c)的需求减少111而(r1,c1)(r1,c1)(r1,c1)的需求减少111。重复该过程直到(r,c)(r,c)(r,c)变为蓝色dr,c0d_{r,c} 0dr,c​0。处理完(r,c)(r,c)(r,c)后如果(r1,c1)(r1,c1)(r1,c1)也已蓝且rn−1r n-1rn−1则整个金字塔已处理完毕返回。否则执行一次单独的3\texttt{3}3跳到(r1,c1)(r1,c1)(r1,c1)将其需求减111然后沿左下方向1\texttt{1}1一步一步向下移动到底部第nnn行。最后递归调用dfs(n,c1)\texttt{dfs}(n, c1)dfs(n,c1)处理下一列。非对角线格子(rc)(r c)(rc)此时(r,c)(r,c)(r,c)和其右上邻居(r−1,c)(r-1, c)(r−1,c)为一对。反复执行“右上→\to→左下”91\texttt{9} \texttt{1}91的组合第一步9\texttt{9}9跳到(r−1,c)(r-1, c)(r−1,c)第二步1\texttt{1}1跳回(r,c)(r, c)(r,c)。同样每往返一次(r,c)(r,c)(r,c)的需求减111(r−1,c)(r-1,c)(r−1,c)的需求也减111。重复直至(r,c)(r,c)(r,c)变蓝。执行一次单独的9\texttt{9}9跳到(r−1,c)(r-1, c)(r−1,c)然后递归调用dfs(r−1,c)\texttt{dfs}(r-1, c)dfs(r−1,c)继续处理上一行。起始位置的选择先以底部最左侧(n,1)(n, 1)(n,1)为起点调用dfs(n,1)\texttt{dfs}(n, 1)dfs(n,1)。如果最终右下角(n,n)(n, n)(n,n)不是蓝色说明该起点不能直接成功。此时改为从(n−1,1)(n-1, 1)(n−1,1)出发先向下跳一步1\texttt{1}1改变(n,1)(n, 1)(n,1)的颜色再恢复初始颜色备份重新调用dfs(n,1)\texttt{dfs}(n, 1)dfs(n,1)。这样可以保证构造成功。正确性保证递归过程中每次往返操作只改变当前格及其斜上方/斜下方同伴的颜色不影响已经处理好的上方区域。通过按列和行的严格顺序所有格子都能被恰当地消除需求。由于总跳跃次数与每个格子的需求成正比最大需求为222每个格子最多被处理常数次总长度远小于500050005000。此构造方法利用了金字塔的几何限制只能垂直方向跳跃使得局部操作不会扩散到其他列。复杂度分析每组测试用例的时间复杂度为O(n2)O(n^2)O(n2)主要来自递归调用和对每个格子的常数次操作。空间复杂度为O(n2)O(n^2)O(n2)用于存储颜色状态和跳跃序列。由于n≤40n \le 40n≤40完全足够。代码实现// Pyramid// UVa ID: 10632// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN55;intn;intcol[MAXN][MAXN];// 当前颜色 0R,1G,2Bintbackup[MAXN][MAXN];// 初始颜色备份vectorintpath;// 存储跳跃方向数字// 递归构造跳跃序列voiddfs(intr,intc){if(rncn)return;if(rc){// 对角线上的格子intnrr1,ncc1;// 通过来回跳跃将 (r,c) 变成蓝色while(col[r][c]!2){path.push_back(3);// 右下path.push_back(7);// 左上col[nr][nc](col[nr][nc]1)%3;col[r][c](col[r][c]1)%3;}// 若已经到达底部倒数第二格且右下角已是蓝色结束if(col[nr][nc]2rn-1cn-1)return;// 跳向右下方处理下一列path.push_back(3);col[nr][nc](col[nr][nc]1)%3;// 沿着左边向下移动到底部while(nrn){path.push_back(1);// 左下nr;col[nr][nc](col[nr][nc]1)%3;}dfs(n,c1);}else{// 非对角线 (r c)intnrr-1,ncc;// 通过来回跳跃将 (r,c) 变成蓝色while(col[r][c]!2){path.push_back(9);// 右上path.push_back(1);// 左下col[nr][nc](col[nr][nc]1)%3;col[r][c](col[r][c]1)%3;}// 跳向右上方继续处理上一行path.push_back(9);col[nr][nc](col[nr][nc]1)%3;dfs(nr,nc);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);while(cinnn!0){// 读入初始配置for(inti1;in;i){string s;cins;for(intj1;ji;j){charchs[j-1];intval(chR?0:(chG?1:2));backup[i][j]col[i][j]val;}}path.clear();dfs(n,1);// 尝试从底部最左出发intstartRow;if(col[n][n]!2){// 若右下角未变蓝从上一行重新开始path.clear();path.push_back(1);// 先向下跳一步backup[n][1](backup[n][1]1)%3;for(inti1;in;i)for(intj1;ji;j)col[i][j]backup[i][j];dfs(n,1);startRown-1;}else{startRown;}coutstartRow 1\n;for(intd:path)coutchar(d0);cout\n;}return0;}总结本题是一道构造性极强的题目关键观察点是金字塔跳跃只能影响相邻上下行而且颜色变化只有三种状态。利用“对角线”和“非对角线”两种局部的来回跳跃模式我们可以像“消消乐”一样从底部开始逐个清空格子的需求同时确保不破坏已处理区域。递归调用使得代码结构清晰方向字符与几何跳转一一对应。这种利用局部操作逐步归约的构造方法在处理有限状态的网格问题时往往能发挥奇效。