题解 P1535 【[USACO08MAR]Cow Travelling S】

Phoenix_chaser · 2020-11-21 23:21:48 · 题解

其实这题不需要记搜

本题题意大概就是问你在T时有多少条路可以到r2,c2

这也为我们的搜索提供了一个回溯的时间：

如果时间大于T直接回溯

于是我们写了这样一个搜索：

void dfs(int x,int y,int t){
    if(t==T){
        if(x==r2&&y==c2) 
        ans++; 
        return ;
    }

    if(a[x+1][y]==1)dfs(x+1,y,t+1);
    if(a[x-1][y]==1)dfs(x-1,y,t+1);
    if(a[x][y+1]==1)dfs(x,y+1,t+1);
    if(a[x][y-1]==1)dfs(x,y-1,t+1);
}

提交之后得了80pts,真不戳竟然得了这么多分，于是本蒟蒻就不停的剪枝，终于拿到了100分。

其实还是从时间限制入手，仔细思考后我们发现：

如果剩余的时间比现在处点与目标点距离要少，那么就没有必要再继续去了。

if(as(x-r2)+as(y-c2)>T-t)

return ;

就是上面这句

加了就ac了

完整代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,T,a[1004][1004],r1,c1,r2,c2,ans=0;
char c;
int as(int x){
    if(x<=0) return -x;
    else return x;
}
void dfs(int x,int y,int t){
    if(t==T){
        if(x==r2&&y==c2) 
        ans++; 
        return ;
    }
    if(as(x-r2)+as(y-c2)>T-t)
    return ;
    if(a[x+1][y]==1)dfs(x+1,y,t+1);
    if(a[x-1][y]==1)dfs(x-1,y,t+1);
    if(a[x][y+1]==1)dfs(x,y+1,t+1);
    if(a[x][y-1]==1)dfs(x,y-1,t+1);
}
int main(){
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c;
            if(c=='.') a[i][j]=1;
            else a[i][j]=0;
        }
    }
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    dfs(r1,c1,0);
    printf("%d",ans);

}

谢谢观看