题目描述机器人在一块发光网格上移动。初始时所有格子都是暗的每当机器人走过一个格子该格子就会亮起并且只要机器人继续移动灯光就会保持亮着。机器人只能执行两种动作a沿当前方向前进一步b顺时针旋转90∘90^\circ90∘并前进一步。机器人总是从网格的左下角出发初始面朝上朝向网格顶部。它可以执行任意由a和b组成的动作序列可以连续多次执行同一动作也可以任意交替但必须满足不能离开网格边界不能经过之前已经亮过的格子即每个格子最多经过一次。机器人在任何时候只要可能移动就会继续只有到达一个无法再执行任何动作的格子时才会停止此时该路径结束。问对于给定的网格机器人一共能走出多少条不同的终止路径输入格式第一行包含一个整数TTT表示测试用例数。接下来TTT行每行包含两个整数RRR和CCC分别表示网格的行数和列数2≤R≤252 \le R \le 252≤R≤251≤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中排列的不同序列数。解题思路组合计数路径总数等于二项式系数(RC−2R−1)(RC−2C−1) \binom{RC-2}{R-1} \binom{RC-2}{C-1}(R−1RC−2)(C−1RC−2)其中RC−2RC-2RC−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。对于每个测试用例直接输出(RC−2R−1)\binom{RC-2}{R-1}(R−1RC−2)即可。复杂度分析预处理组合数O(502)O(50^2)O(502)与输入规模无关。每个测试用例回答O(1)O(1)O(1)。总时间复杂度O(502T)O(50^2 T)O(502T)空间复杂度O(502)O(50^2)O(502)。代码实现// The Robots Grid// UVa ID: 13214// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;longlongcomb[50][50];voidinitComb(){for(inti0;i50;i){comb[i][0]comb[i][i]1;for(intj1;ji;j)comb[i][j]comb[i-1][j-1]comb[i-1][j];}}intmain(){initComb();intT;scanf(%d,T);while(T--){intR,C;scanf(%d %d,R,C);intnRC-2;intkR-1;// 也可用 min(R-1, C-1)printf(%lld\n,comb[n][k]);}return0;}总结本题的核心在于识别出机器人路径的单调性将几何路径计数转化为组合数问题。关键观察点包括只能右转且不能重复格子的限制迫使其路径只能向上和向右任意向上/向右的序列都能被机器人执行且对应唯一路径组合数计算简单且高效避免了搜索的指数复杂度。这类问题提醒我们在面对看似复杂的搜索问题时应首先尝试挖掘数学结构往往能大幅简化计算。同时注意数据范围选择合适的数据类型避免溢出。
