题目描述
在一个经典的电脑游戏中，一个生物在金字塔形状的格子上跳跃。金字塔共有 nnn 行，第 iii 行有 iii 个格子。生物每次只能跳到其正上方或正下方的相邻格子，不能跳出金字塔。当生物落在一个格子上时，该格子的颜色会按照 红色 →\\to→ 绿色 →\\to→ 蓝色 →\\to→ 红色 的顺序循环改变。
给定每个格子的初始颜色（R、G、B），需要找到一个不超过 500050005000 次跳跃的序列，使得所有格子最终都变为蓝色。你可以选择金字塔中任意一个格子作为起点（保证解总是存在），第一次改变颜色的格子是跳跃后落地的格子。
输入格式
输入包含多组测试用例，最多 505050 组。
每组测试用例的第一行是一个整数 nnn（2≤n≤402 \\le n \\le 402≤n≤40），表示金字塔的高度。
接下来 nnn 行描述金字塔的初始配置，每行由大写字母 R、G、B 组成，代表该行从左到右的颜色。
输入以 n=0n = 0n=0 结束，该行不处理。
输出格式
对于每组测试用例，输出两行。
第一行包含两个整数，表示起始位置：第一个整数为行号（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×412=820\\frac{40 \\times 41}{2} = 820240×41=820 个，而跳跃次数上限为 500050005000，这意味着我们可以采用一种系统性的构造方法，而不是搜索最短路。关键在于找到一种能够“逐个消灭”格子需求的操作模式，同时保证过程中不会将已经变蓝的格子再次弄乱。
观察金字塔的几何结构：除了顶部的第 111 行和第 222 行之外，其余行都可以通过特定的模式操作，在不破坏上方已处理格子的前提下，将当前行的格子逐一变为蓝色。递归地自底向上处理即可。
解题思路
本题解采用自底向上、按列归约的递归构造。核心思想是：将金字塔从底部到顶部逐行处理，对于当前行的每一个格子，利用其与“右上方”或“左上方”邻格的来回跳跃，在不影响更上方格子的前提下将其变蓝。
颜色与方向编码
将颜色映射为整数：R →0\\to 0→0，G →1\\to 1→1，B →2\\to 2→2。目标颜色为 222。用 dr,c=(2−color+3) mod 3d_{r,c} = (2 – \\text{color} + 3) \\bmod 3dr,c=(2−color+3)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)→(r+1,c)(r,c) \\to (r+1, c)(r,c)→(r+1,c)
- 3\\texttt{3}3：向右下方，(r,c)→(r+1,c+1)(r,c) \\to (r+1, c+1)(r,c)→(r+1,c+1)
递归函数的定义
递归函数 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)（金字塔底部右下角）或某个特定位置，便于上层调用。
递归分两种情况：
对角线格子 (r=c)(r = c)(r=c)
此时 (r,c)(r,c)(r,c) 和其右下方邻居 (r+1,c+1)(r+1, c+1)(r+1,c+1) 构成一对。
- 首先，反复执行“右下 →\\to→ 左上”（3+7\\texttt{3} + \\texttt{7}3+7）的组合：
- 第一步 3\\texttt{3}3 跳到 (r+1,c+1)(r+1, c+1)(r+1,c+1)，落地将其需求减 111；
- 第二步 7\\texttt{7}7 跳回 (r,c)(r, c)(r,c)，落地将其需求减 111。
这样一次往返恰好让 (r,c)(r,c)(r,c) 的需求减少 111，而 (r+1,c+1)(r+1,c+1)(r+1,c+1) 的需求减少 111。
重复该过程直到 (r,c)(r,c)(r,c) 变为蓝色（dr,c=0d_{r,c} = 0dr,c=0）。
- 处理完 (r,c)(r,c)(r,c) 后，如果 (r+1,c+1)(r+1,c+1)(r+1,c+1) 也已蓝且 r=n−1r = n-1r=n−1，则整个金字塔已处理完毕，返回。
- 否则，执行一次单独的 3\\texttt{3}3 跳到 (r+1,c+1)(r+1,c+1)(r+1,c+1)（将其需求减 111），然后沿左下方向（1\\texttt{1}1）一步一步向下移动到底部第 nnn 行。
- 最后递归调用 dfs(n,c+1)\\texttt{dfs}(n, c+1)dfs(n,c+1)，处理下一列。
非对角线格子 (r>c)(r > c)(r>c)
此时 (r,c)(r,c)(r,c) 和其右上邻居 (r−1,c)(r-1, c)(r−1,c) 为一对。
- 反复执行“右上 →\\to→ 左下”（9+1\\texttt{9} + \\texttt{1}9+1）的组合：
- 第一步 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
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int n;
int col[MAXN][MAXN]; // 当前颜色 0=R,1=G,2=B
int backup[MAXN][MAXN]; // 初始颜色备份
vector<int> path; // 存储跳跃方向数字
// 递归构造跳跃序列
void dfs(int r, int c) {
if (r == n && c == n) return;
if (r == c) { // 对角线上的格子
int nr = r + 1, nc = c + 1;
// 通过来回跳跃将 (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] == 2 && r == n – 1 && c == n – 1) return;
// 跳向右下方，处理下一列
path.push_back(3);
col[nr][nc] = (col[nr][nc] + 1) % 3;
// 沿着左边向下移动到底部
while (nr < n) {
path.push_back(1); // 左下
nr++;
col[nr][nc] = (col[nr][nc] + 1) % 3;
}
dfs(n, c + 1);
} else { // 非对角线 (r > c)
int nr = r – 1, nc = c;
// 通过来回跳跃将 (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);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> n && n != 0) {
// 读入初始配置
for (int i = 1; i <= n; ++i) {
string s; cin >> s;
for (int j = 1; j <= i; ++j) {
char ch = s[j – 1];
int val = (ch == 'R' ? 0 : (ch == 'G' ? 1 : 2));
backup[i][j] = col[i][j] = val;
}
}
path.clear();
dfs(n, 1); // 尝试从底部最左出发
int startRow;
if (col[n][n] != 2) { // 若右下角未变蓝，从上一行重新开始
path.clear();
path.push_back(1); // 先向下跳一步
backup[n][1] = (backup[n][1] + 1) % 3;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
col[i][j] = backup[i][j];
dfs(n, 1);
startRow = n – 1;
} else {
startRow = n;
}
cout << startRow << " 1\\n";
for (int d : path) cout << char(d + '0');
cout << "\\n";
}
return 0;
}
总结
本题是一道构造性极强的题目，关键观察点是金字塔跳跃只能影响相邻上下行，而且颜色变化只有三种状态。利用“对角线”和“非对角线”两种局部的来回跳跃模式，我们可以像“消消乐”一样，从底部开始逐个清空格子的需求，同时确保不破坏已处理区域。递归调用使得代码结构清晰，方向字符与几何跳转一一对应。这种利用局部操作逐步归约的构造方法，在处理有限状态的网格问题时往往能发挥奇效。
