题解 P1535 【游荡的奶牛】

henry_y · 2018-07-21 23:06:49 · 题解

唔这道题不想说什么了，挺水的，不过，部分分做法也讲一下

都是dfs的，这个最容易想

40分做法

爆搜，只要注意判边界和会不会撞到树就好了

void dfs(int x,int y,int now){
    if(x<1||x>n||y<1||y>m||now>T)return;
    if(now==T&&x==xx&&y==yy){ans++;return;}
    for(int i=0;i<=3;i++)
        if(a[x+dx[i]][y+dy[i]])
            dfs(x+dx[i],y+dy[i],now+1);
}

90分做法

加一个小小的剪枝，如果当前点距离目标点的曼哈顿距离比剩下的步数还大，就肯定到不了，所以就直接return掉

即如果 abs(x-xx)+abs(y-yy)>T-now 那就return

这样就能90

void dfs(int x,int y,int now){
    if(abs(x-xx)+abs(y-yy)>T-now)return;
    if(x<1||x>n||y<1||y>m||now>T)return;
    if(now==T&&x==xx&&y==yy){ans++;return;}
    for(int i=0;i<=3;i++)
        if(a[x+dx[i]][y+dy[i]])
            dfs(x+dx[i],y+dy[i],now+1);
}

100分做法

90分做法开一下O2就好

Code：

#include <cstdio>
using namespace std;
int n,m,T,X,Y,xx,yy,ans=0;
int a[110][110];
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int abs(int x){return x>=0?x:-x;}
void dfs(int x,int y,int now){
    if(abs(x-xx)+abs(y-yy)>T-now)return;
    if(x<1||x>n||y<1||y>m||now>T)return;
    if(now==T&&x==xx&&y==yy){ans++;return;}
    for(int i=0;i<=3;i++)
        if(a[x+dx[i]][y+dy[i]])
            dfs(x+dx[i],y+dy[i],now+1);
}
int main(){
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++){
        char s[110];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            a[i][j]=(s[j]=='.'?1:0);
        }
    }
    scanf("%d%d%d%d",&X,&Y,&xx,&yy);
    dfs(X,Y,0);
    printf("%d",ans);
    return 0;
}