P4825 [USACO15FEB]Cow Hopscotch S 题解

· · 题解

upd on 2024.8.23：第 28 行修改为 for (int j = 2; j <= c; j++)。感谢@Hollow_Knight 的指出

本题暴力的思路是：枚举每一个点，看看有哪些点可以到达这个点，这个点的方案数就是所有能到达它的点的方案数之和。

现在关键是要求有哪些点可以到达一个点了。在这个点的左上方的点都可以到达这一个点。因为题目说的是 至少。

至于第一个条件，在循环里特判一下就可以了。

这道题的加强版是一道蓝题，要用线段树，数据范围是 r,c \leq 750 ， 过不了。但是这道题的范围是 r,n \leq100 ，所以我们就直接暴力就行了。

代码：

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;
int a[105][105], dp[105][105];
int read()
{
    int i = 0, f = 1;
    char ch;
    for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if (ch == '-')
    {
        f = -1;
        ch = getchar();
    }
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch ^ 48);
    return i * f;
}
signed main()
{
    int r = read(), c = read(), k = read();
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            a[i][j] = read();
    dp[1][1] = 1;
    for (int i = 2; i <= r; i++)
        for (int j = 2; j <= c; j++)
            for (int t1 = 1; t1 < i; t1++)
                for (int t2 = 1; t2 < j; t2++)
                    if (a[t1][t2] != a[i][j]) dp[i][j] = (dp[i][j] + dp[t1][t2]) % mod;
    printf("%lld", dp[r][c]);
    return 0;
}