题解 P1535 【游荡的奶牛】

· · 题解

才发现普及+的题如此简单...完全刷新对普及+的印象

今天不知A了多少绿题了

步入正题

思路历程

普通爆搜思路

这题普通爆搜思路很好想

总而言之就是在规定的步数T内

有几种从出发点到目标点的方法

首先从出发点开始搜

向上下左右四个方向搜索（很显然的说）

那么就只要到达目的地ans++

这是一个40分程序

#include<iostream> 
using namespace std;
int n,m,t,x1,y1,x2,y2;
int X[4]={1,-1,0,0},Y[4]={0,0,1,-1};
bool ok[110][110];
int ans;
inline bool pd(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m)
    if(ok[x][y])return 1;
    return 0;
}
inline void dfs(int x,int y,int time){
    if(x==x2&&y==y2&&time==0)ans++;
    if(!time)return;
    int i;
    for(i=0;i<4;i++)
    if(pd(x+X[i],y+Y[i]))
    dfs(x+X[i],y+Y[i],time-1);
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    int i,j,k;
    char c;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){cin>>c;if(c=='.')ok[i][j]=1;else ok[i][j]=0;}
    cin>>x1>>y1>>x2>>y2;
    dfs(x1,y1,t);
    cout<<ans;
}

很显然普通的爆搜是注定要T的

那么须要一个剪枝

可行性剪枝：如果在T次之内无法到达目的地

return

下面是90分程序

#include<iostream> 
using namespace std;
int n,m,t,x1,y1,x2,y2;
int X[4]={1,-1,0,0},Y[4]={0,0,1,-1};
bool ok[110][110];
int ans;
inline bool pd(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m)
    if(ok[x][y])return 1;
    return 0;
}
inline int abs(int s){
    if(s<0)return -s;
    return s;
}
inline void dfs(int x,int y,int time){
    if(x==x2&&y==y2&&time==0)ans++;
    if(!time||abs(x-x2)+abs(y-y2)>time)return;
    int i;
    for(i=0;i<4;i++)
    if(pd(x+X[i],y+Y[i]))
    dfs(x+X[i],y+Y[i],time-1);
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    int i,j,k;
    char c;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){cin>>c;if(c=='.')ok[i][j]=1;else ok[i][j]=0;}
    cin>>x1>>y1>>x2>>y2;
    dfs(x1,y1,t);
    cout<<ans;
}

找了许久（3分钟）

发现过多次调用函数 is a waste of time

只要删除pd函数就AC了

100分程序

#include<iostream> 
using namespace std;
int n,m,t,x1,y1,x2,y2;
int X[4]={1,-1,0,0},Y[4]={0,0,1,-1};
bool ok[110][110];
int ans;
inline int abs(int s){
    if(s<0)return -s;
    return s;
}
inline void dfs(int x,int y,int time){
    if(x==x2&&y==y2&&time==0)ans++;
    if(!time||abs(x-x2)+abs(y-y2)>time)return;
    int i;
    for(i=0;i<4;i++)
    if(x>=1&&x<=n&&y>=1&&y<=m&&ok[x][y])
    dfs(x+X[i],y+Y[i],time-1);
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    int i,j,k;
    char c;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){cin>>c;if(c=='.')ok[i][j]=1;else ok[i][j]=0;}
    cin>>x1>>y1>>x2>>y2;
    dfs(x1,y1,t);
    cout<<ans;
}

人走可以，把赞留下