[USACO 2015 February Bronze] Cow Hopscotch 题解

题目大意

在一个 $R \times C$ 的网格上，每个格子被涂成红色(R)或蓝色(B)。奶牛从左上角 $(1,1)$ 出发，要到达右下角 $(R,C)$。每次跳跃必须满足以下条件：

1. 跳到不同颜色的格子
2. 跳到的格子行数必须严格大于当前位置的行数
3. 跳到的格子列数必须严格大于当前位置的列数

求从起点到终点的不同路径数。

数据范围分析

• $2 \leq R \leq 15$
• $2 \leq C \leq 15$

由于网格最多只有 $15 \times 15 = 225$ 个格子，因此可以使用暴力搜索（DFS）来解决。

算法分析

深度优先搜索（DFS）解法

题目给出的代码使用了深度优先搜索来枚举所有可能的路径。思路如下：

1. 从起点 $(1,1)$ 开始搜索
2. 对于当前位置 $(x,y)$，枚举所有满足条件的下一步位置 $(i,j)$：
   • $i > x$（行数增加）
   • $j > y$（列数增加）
   • $a[i][j] \neq a[x][y]$（颜色不同）
3. 如果到达终点 $(R,C)$，则路径数加1
4. 继续搜索直到遍历完所有可能路径

时间复杂度分析

在最坏情况下，每个格子都可以跳到它右下方的所有格子。对于 $15 \times 15$ 的网格，状态空间虽然较大，但由于限制条件较严格（只能向右下方移动），实际可探索的路径数是有限的，DFS 可以在可接受时间内完成。

状态表示

• a[i][j]: 存储网格颜色
• vis[i][j]: 记录是否访问过该位置（虽然本题中路径不会重复访问同一格子，但这是DFS的常见写法）
• cnt: 记录到达终点的路径总数

代码详解

#include<iostream>
using namespace std;

int n, m, cnt = 0;  // n:行数，m:列数，cnt:路径计数
char a[50][50];     // 存储网格颜色
bool vis[50][50];   // 访问标记数组

// 深度优先搜索函数
// x,y: 当前位置
// z: 当前位置的颜色
void dfs(int x, int y, char z) {
    // 如果到达终点
    if(x == n && y == m) {
        cnt++;  // 路径数加1
        return;
    }
    
    // 枚举所有可能的下一步
    for(int i = x + 1; i <= n; i++) {        // 行必须增加
        for(int j = y + 1; j <= m; j++) {    // 列必须增加
            if(a[i][j] != z) {               // 颜色必须不同
                vis[i][j] = 1;               // 标记访问
                dfs(i, j, a[i][j]);          // 递归搜索
                vis[i][j] = 0;               // 回溯，取消标记
            }
        }
    }
}

int main() {
    // 输入网格大小
    cin >> n >> m;
    
    // 输入网格颜色
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 从起点开始搜索
    vis[1][1] = 1;                   // 标记起点已访问
    dfs(1, 1, a[1][1]);              // 开始DFS搜索
    cout << cnt;                     // 输出结果
    
    return 0;
}

示例分析

示例输入

4 4
RRRR
RRBR
RBBR
RRRR

网格颜色分布

(1,1)R  (1,2)R  (1,3)R  (1,4)R
(2,1)R  (2,2)R  (2,3)B  (2,4)R
(3,1)R  (3,2)B  (3,3)B  (3,4)R
(4,1)R  (4,2)R  (4,3)R  (4,4)R

可能的路径分析

从起点 (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)$ 的路径数。

状态转移方程：

$$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[1][1] = 1

最终答案：dp[R][C]

这种解法的时间复杂度为 $O(R^2 \times C^2)$，对于 $R,C \leq 15$ 也是可行的。

注意事项

1. 只能向右下方移动，不能向左或向上
2. 必须跳到不同颜色的格子
3. 起点和终点颜色可能相同也可能不同
4. 路径可以跳过多个格子，不一定要逐格移动

总结

本题是一道典型的网格路径计数问题，由于数据范围较小，可以使用DFS暴力搜索。解题关键点：

1. 理解跳跃规则：只能向右下方向，且必须改变颜色
2. 使用DFS枚举所有可能路径
3. 注意回溯时要恢复状态

对于更大的数据范围，建议使用动态规划或其他更高效的算法。