[USACO 2015 FEBRUARY BRONZE] COW HOPSCOTCH 题解
题目大意
在一个 R×CR \times CR×C 的网格上，每个格子被涂成红色(R)或蓝色(B)。奶牛从左上角 (1,1)(1,1)(1,1) 出发，要到达右下角 (R,C)(R,C)(R,C)。每次跳跃必须满足以下条件：
1. 跳到不同颜色的格子
2. 跳到的格子行数必须严格大于当前位置的行数
3. 跳到的格子列数必须严格大于当前位置的列数
求从起点到终点的不同路径数。
数据范围分析
* 2≤R≤152 \leq R \leq 152≤R≤15
* 2≤C≤152 \leq C \leq 152≤C≤15
由于网格最多只有 15×15=22515 \times 15 = 22515×15=225 个格子，因此可以使用暴力搜索（DFS）来解决。
算法分析
深度优先搜索（DFS）解法
题目给出的代码使用了深度优先搜索来枚举所有可能的路径。思路如下：
1. 从起点 (1,1)(1,1)(1,1) 开始搜索
2. 对于当前位置 (x,y)(x,y)(x,y)，枚举所有满足条件的下一步位置 (i,j)(i,j)(i,j)：
* i>xi > xi>x（行数增加）
* j>yj > yj>y（列数增加）
* a[i][j]≠a[x][y]a[i][j] \neq a[x][y]a[i][j]=a[x][y]（颜色不同）
3. 如果到达终点 (R,C)(R,C)(R,C)，则路径数加1
4. 继续搜索直到遍历完所有可能路径
时间复杂度分析
在最坏情况下，每个格子都可以跳到它右下方的所有格子。对于 15×1515 \times 1515×15 的网格，状态空间虽然较大，但由于限制条件较严格（只能向右下方移动），实际可探索的路径数是有限的，DFS 可以在可接受时间内完成。
状态表示
* a[i][j]: 存储网格颜色
* vis[i][j]: 记录是否访问过该位置（虽然本题中路径不会重复访问同一格子，但这是DFS的常见写法）
* cnt: 记录到达终点的路径总数
代码详解
示例分析
示例输入
网格颜色分布
可能的路径分析
从起点 (1,1)R 出发：
1. 路径1: (1,1)R → (2,3)B → (4,4)R
2. 路径2: (1,1)R → (3,2)B → (4,4)R
3. 路径3: (1,1)R → (3,4)R → 无法继续（颜色相同）
（注：实际只有前两条有效路径到达终点）
输出结果为 3，说明有3条不同的路径。
优化思路
虽然本题数据范围较小，DFS可以直接通过，但我们也可以考虑使用动态规划（DP）来优化：
动态规划解法
设 dp[i][j] 表示到达位置 (i,j)(i,j)(i,j) 的路径数。
状态转移方程：
dp[i][j]=∑x=1i−1∑y=1j−1dp[x][y](当 a[i][j]≠a[x][y] 时)dp[i][j] = \sum_{x=1}^{i-1}\sum_{y=1}^{j-1} dp[x][y] \quad (\text{当 } a[i][j] \neq a[x][y] \text{ 时}) dp[i][j]=x=1∑i−1 y=1∑j−1 dp[x][y](当 a[i][j]=a[x][y] 时)
初始条件：dp[1][1] = 1
最终答案：dp[R][C]
这种解法的时间复杂度为 O(R2×C2)O(R^2 \times C^2)O(R2×C2)，对于 R,C≤15R,C \leq 15R,C≤15 也是可行的。
注意事项
1. 只能向右下方移动，不能向左或向上
2. 必须跳到不同颜色的格子
3. 起点和终点颜色可能相同也可能不同
4. 路径可以跳过多个格子，不一定要逐格移动
总结
本题是一道典型的网格路径计数问题，由于数据范围较小，可以使用DFS暴力搜索。解题关键点：
1. 理解跳跃规则：只能向右下方向，且必须改变颜色
2. 使用DFS枚举所有可能路径
3. 注意回溯时要恢复状态
对于更大的数据范围，建议使用动态规划或其他更高效的算法。
