P1535 [USACO08MAR] Cow Travelling S

Reading the Problem

P1535 [USACO08MAR] Cow Travelling S - Luogu | New Ecology of Computer Science Education (luogu.com.cn)

The problem roughly says: a cow moves around inside a rectangle of a given size. The cells are either grass or trees, and the cow cannot walk on trees.

In one move, the cow can go up, down, left, or right, but cannot stay in place (though it can go in circles!). Given two points A and B, count the number of paths from A to B that take exactly T steps.

There’s a slight issue with the original problem statement—maybe it’s a translation problem. The original text says “within T seconds,” but what it actually wants is exactly that T-th second. It took me forever to find the bug; I only noticed it after checking the discussion board.

Approach

At first I thought of using BFS, searching until the front element’s time reaches t+1. But trying it gave MLE, and I didn’t feel like optimizing with memoization or anything.

Then it hit me: the number of ways to reach each cell at each moment is like a “slice,” and the recurrence between different times and coordinates is obvious. The number of paths at a given time equals the sum of the path counts from the four neighboring cells at the previous time. Of course, if the cell is a tree, it’s 0. From this, we can write the DP formula:

$$
dp[x][y][t] =
\begin{cases}
0 & \text{if } \text{block}[x][y] = 1 \
dp[x-1][y][t-1] + dp[x+1][y][t-1] + dp[x][y-1][t-1] + dp[x][y+1][t-1] & \text{otherwise}
\end{cases}
$$

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <bits/stdc++.h>
using namespace std;

int n, m, t;
int block[110][110]{0};  // 0未被阻挡
int dp[110][110][16]{0};

bool is_valid(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m && !block[x][y];
}

int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            block[i][j] = (c == '*' ? 1 : 0);
        }
    }
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    dp[x1][y1][0] = 1;
    for (int k = 1; k <= t; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (is_valid(i, j))
                {
                    if (is_valid(i - 1, j)) dp[i][j][k] += dp[i - 1][j][k - 1];
                    if (is_valid(i + 1, j)) dp[i][j][k] += dp[i + 1][j][k - 1];
                    if (is_valid(i, j - 1)) dp[i][j][k] += dp[i][j - 1][k - 1];
                    if (is_valid(i, j + 1)) dp[i][j][k] += dp[i][j + 1][k - 1];
                }
            }
        }
    }

    int ans = 0;

    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = 0; j < m; j++)
    //     {
    //         cout << dp[i][j][1] << ' ';
    //     }
    //     cout << '\n';
    // }

    cout << dp[x2][y2][t] << endl;
    system("pause");
    return 0;
}