UVa 13214 The Robot‘s Grid

发布时间：2026/11/4 1:57:58

题目描述

机器人在一块发光网格上移动。初始时所有格子都是暗的，每当机器人走过一个格子，该格子就会亮起，并且只要机器人继续移动，灯光就会保持亮着。

机器人只能执行两种动作：

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>usingnamespacestd;longlongcomb[50][50];voidinitComb(){for(inti=0;i<50;++i){comb[i][0]=comb[i][i]=1;for(intj=1;j<i;++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);intn=R+C-2;intk=R-1;// 也可用 min(R-1, C-1)printf("%lld\n",comb[n][k]);}return0;}