UVa 13214 The Robot‘s Grid
题目描述
机器人在一块发光网格上移动。初始时所有格子都是暗的，每当机器人走过一个格子，该格子就会亮起，并且只要机器人继续移动，灯光就会保持亮着。
机器人只能执行两种动作：
a：沿当前方向前进一步；b：顺时针旋转 90∘90^\circ90∘ 并前进一步。
机器人总是从网格的左下角出发，初始面朝上（朝向网格顶部）。它可以执行任意由 a 和 b 组成的动作序列（可以连续多次执行同一动作，也可以任意交替），但必须满足：
- 不能离开网格边界；
- 不能经过之前已经亮过的格子（即每个格子最多经过一次）。
机器人在任何时候只要可能移动就会继续，只有到达一个无法再执行任何动作的格子时才会停止，此时该路径结束。
问：对于给定的网格，机器人一共能走出多少条不同的终止路径？
输入格式
第一行包含一个整数 TTT ，表示测试用例数。
接下来 TTT 行，每行包含两个整数 RRR 和 CCC ，分别表示网格的行数和列数（2≤R≤252 \le R \le 252≤R≤25 ，1≤C≤251 \le C \le 251≤C≤25）。
输出格式
对于每个测试用例，输出一行一个整数，表示不同路径的数量。
样例
输入
4
2 1
2 2
2 3
3 3
输出
1
2
3
6
题目分析
本题表面上是搜索问题，但网格规模最大为 25×2525 \times 2525×25 ，若使用深度优先搜索暴力枚举所有可能路径，状态数会指数爆炸，不可行。需要挖掘问题的数学本质。
机器人只能直走或右转，不能左转，且路径不能自交。在矩形网格中，这种“仅右转”的自回避路径（俗称螺旋路径）具有非常强的结构限制。
从起点（左下角）出发，初始方向朝上。每一步要么直走，要么右转后走一步。这意味着路径的走向序列只能由向上（UUU）和向右（RRR）组成，因为一旦右转，方向变为向右，之后若再右转则方向向下，但向下移动必然会导致路径自交或离开边界（因为机器人只会前进，不会后退，且不能重复格子）。事实上，可以证明：合法的终止路径必然从起点到终点（右上角）只使用向右和向上的移动，且路径是单调的，即每一步要么向右，要么向上。
为什么不能向左或向下？因为初始朝上，第一次右转后朝右，再右转朝下，但朝下走会回到已经走过的行（因为之前已向上走过），必然经过已亮格子，违反规则。唯一可能不经过已亮格子的朝下移动仅发生在路径已经占据了所有可能的上方格子，但这样路径会被封死而提前终止，无法到达终点。因此，所有完整路径实际上都是单调的，仅包含 R−1R-1R−1 个向上步和 C−1C-1C−1 个向右步。
更进一步，任何一个由 R−1R-1R−1 个 UUU 和 C−1C-1C−1 个 RRR 组成的序列都对应一条合法的机器人路径。机器人只需依次执行这些步骤，每次需要右转时执行 b 动作，否则执行 a 动作。该路径不会重复格子，因为每一步都增加了行号或列号，是严格单调的。因此，路径数量等于从 R−1R-1R−1 个 UUU 和 C−1C-1C−1 个 RRR 中排列的不同序列数。
解题思路
组合计数
路径总数等于二项式系数：
(R+C−2R−1)=(R+C−2C−1) \binom{R+C-2}{R-1} = \binom{R+C-2}{C-1} (R−1R+C−2)=(C−1R+C−2)
其中 R+C−2R+C-2R+C−2 是总步数（向上 R−1R-1R−1 步，向右 C−1C-1C−1 步），选择哪些步是向上即可确定整条路径。
数据范围与精度
由于 R,C≤25R, C \le 25R,C≤25 ，总步数最多为 484848 ，组合数最大值 (4824)≈3.2×1013\binom{48}{24} \approx 3.2 \times 10^{13}(2448)≈3.2×1013 ，在 646464 位有符号整数范围内（9×10189 \times 10^{18}9×1018），因此使用 long long 类型存储即可。
计算组合数的方法
采用递推方式构造杨辉三角，预处理所有 n≤48n \le 48n≤48 的组合数。递推公式为：
(nk)=(n−1k−1)+(n−1k) \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} (kn)=(k−1n−1)+(kn−1)
边界条件 (n0)=(nn)=1\binom{n}{0} = \binom{n}{n} = 1(0n)=(nn)=1 。
对于每个测试用例，直接输出 (R+C−2R−1)\binom{R+C-2}{R-1}(R−1R+C−2) 即可。
复杂度分析
- 预处理组合数：O(502)O(50^2)O(502) ，与输入规模无关。
- 每个测试用例回答：O(1)O(1)O(1) 。
- 总时间复杂度 O(502+T)O(50^2 + T)O(502+T) ，空间复杂度 O(502)O(50^2)O(502)。
代码实现
// The Robot's Grid
// UVa ID: 13214
// Verdict: Accepted
// Submission Date: 2026-07-12
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
long long comb[50][50];
void initComb() {
for (int i = 0; i < 50; ++i) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; ++j)
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
int main() {
initComb();
int T;
scanf("%d", &T);
while (T--) {
int R, C;
scanf("%d %d", &R, &C);
int n = R + C - 2;
int k = R - 1; // 也可用 min(R-1, C-1)
printf("%lld\n", comb[n][k]);
}
return 0;
}
总结
本题的核心在于识别出机器人路径的单调性，将几何路径计数转化为组合数问题。关键观察点包括：
- 只能右转且不能重复格子的限制，迫使其路径只能向上和向右；
- 任意向上/向右的序列都能被机器人执行，且对应唯一路径；
- 组合数计算简单且高效，避免了搜索的指数复杂度。
这类问题提醒我们，在面对看似复杂的搜索问题时，应首先尝试挖掘数学结构，往往能大幅简化计算。同时，注意数据范围，选择合适的数据类型避免溢出。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
1
0- 0
已为社区贡献9条内容
所有评论(0)