题解 P1535 【[USACO08MAR]Cow Travelling S】

· · 题解

DFS + 剪枝

P1535 [USACO08MAR]Cow Travelling S

首先，这道题我用的是 DFS

dfs函数记三个参数，分别是横纵坐标以及走到当前这个点还有多少步数要走

递归搜索时，横纵坐标向上下左右四个方向分别变化，剩余步数 num 减 1 ，可以看出，当横纵坐标分别等于 (R_2,C_2) 且剩余步数为 0 时，可以计入答案中。

。

。

。

。

。

。

但是这样会 TLE

所以加一个剪枝吧

如果说当前点与终点的横、纵坐标差之和小于剩余步数，那肯定不用继续递归下去了。

虽然这种做法没有考虑“墙”，但是曼哈顿距离都太大，再加上墙的阻拦就更远而无法满足题目要求了。

就这么 AC 了

（只好说洛谷评测姬跑的真快）

核心代码

inline bool exist(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m && mp[x][y] != '*';
}

inline void dfs(int x, int y, int num) {
    if(num < (abs(x - r2) + abs(y - c2))) return ; // 剪枝
    if(x == r2 && y == c2 && num == 0)
        ans ++;
    if(num == 0) return ;
    for (int i = 0; i < 4; ++ i) {
        int tx = x + dx[i], ty = y + dy[i];
        if(exist(tx, ty)) dfs(tx, ty, num - 1);
    }
    return ;
}