[数据结构与算法]P1535 [USACO08MAR]Cow Travelling S-DFS+BFS+剪枝

[USACO08MAR]Cow Travelling S

题目描述

奶牛们在被划分成 $N$ 行 $M$ 列（$2\le N,M\le 100$）的草地上游走， 试图找到整块草地中最美味的牧草。

Farmer John 在某个时刻看见贝茜在位置 $(R_1,C_1)$，恰好 $T$（$0<T\le 15$）秒后，FJ 又在位置 $(R_2,C_2)$ 与贝茜撞了正着。FJ 并不知道在这 $T$ 秒内贝茜是否曾经到过 $(R_2,C_2)$，他能确定的只是，现在贝茜在那里。

设 $S$ 为奶牛在 $T$ 秒内从 $(R_1,C_1)$ 走到 $(R_2,C_2)$ 所能选择的路径总数，FJ 希望有 一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动 $1$ 单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。

现在你拿到了一张整块草地的地形图，其中 . 表示平坦的草地，* 表示挡路的树。你的任务是计算出，一头在 $T$ 秒内从 $(R_1,C_1)$ 移动到 $(R_2,C_2)$ 的奶牛可能经过的路径有哪些。

输入格式

第一行包含 $3$ 个用空格隔开的整数：$N,M,T$。

接下来 $n$ 行：第 $i$ 行为 $M$ 个连续的字符，描述了草地第 $i$ 行各点的情况，保证字符是 . 和 * 中的一个。

最后一行 $4$ 个整数 $R_1,C_1,R_2,C_2$。

输出格式

输出从 $(R_1,C_1)$ 移动到 $(R_2,C_2)$ 的方案数。

样例 #1

样例输入 #1

4 5 6
...*.
...*.
.....
.....
1 3 1 5

样例输出 #1

1

1、原本想直接暴力打，也不使用标记数组，搜索全部可能的情况
40分代码

#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=1e2+10,mod=100003;
const int inf=0x3f3f3f3f;
char mp[N][N];
int n,m,ans;
int T;
int sx,sy,ex,ey;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int dep,int x,int y){
    if(dep>T) return ;
    if(dep==T&&x==ex&&y==ey) {ans++;return;}
    int l,r;
    for(int i=0;i<4;i++){
        l=x+dx[i];r=y+dy[i];
        if(l<1||r<1||l>n||r>m) continue;
        if(mp[l][r]=='*') continue;
        dfs(dep+1,l,r);
    }
}
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    cin>>sx>>sy>>ex>>ey;
    dfs(0,sx,sy);
    printf("%d\n",ans);
    return 0;
}

2、后来想先用广度优先搜索一下，从终点到其他所以能到达的点之间的距离，但是写好之后，交上去只有10分
加了剪枝之后的10分代码

#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=1e2+10,mod=100003;
const int inf=0x3f3f3f3f;
struct E{
    int x,y,u;
};
int d[N][N];//记录到终点的最短距离
bool st[N][N];

char mp[N][N];
int n,m,ans;
int T;
int sx,sy,ex,ey;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void bfs(){//从终点搜索到其他所有点的最端距离
//如果在搜索的过程中发现，此时剩下的步数已经小于了最短距离，则一定不能到达
    memset(d,0x3f,sizeof(d));
    queue<E>q;
    q.push(E{ex,ey,0});
    d[ex][ey]=0;st[ex][ey]=1;
    E nw,nx;
    int x,y,u;
    int l,r;
    while(!q.empty()){
        nw=q.front();q.pop();
        x=nw.x;y=nw.y;u=nw.u;
        for(int i=0;i<4;i++){
            l=x+dx[i];r=y+dy[i];
            if(l<1||r<1||l>n||r>m) continue;
            if(mp[l][r]=='*'||st[l][r]==1) continue;
            st[l][r]=1;d[l][r]=u+1;
            q.push(E{l,r,u+1});
        }
    }
}
void dfs(int dep,int x,int y){
    if(d[x][y]+dep==T) {ans++;return ;}//新加的剪枝
    //if(dep+d[x][y]<T) return ;

    if(dep>T) return ;
    if(dep==T&&x==ex&&y==ey) {ans++;return;}
    int l,r;
    for(int i=0;i<4;i++){
        l=x+dx[i];r=y+dy[i];
        if(l<1||r<1||l>n||r>m) continue;
        if(mp[l][r]=='*') continue;
        dfs(dep+1,l,r);
    }
}
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    cin>>sx>>sy>>ex>>ey;
    bfs();
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         de(d[i][j])
    //     }Pu
    // }
    dfs(0,sx,sy);
    printf("%d\n",ans);
    return 0;
}

3、后来看了一下题解，发现用的剪枝方法比较简单，直接用欧式距离判断
100分代码

#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=1e2+10,mod=100003;
const int inf=0x3f3f3f3f;
char mp[N][N];
int n,m,ans;
int T;
int sx,sy,ex,ey;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
inline int abs(int x){
    if(x<0)return -x;
    return x;
}
void dfs(int dep,int x,int y){
    if(dep==T) {
        if(x==ex&&y==ey){
            ans++;
        }
        return;
    }
    if(abs(x-ex)+abs(y-ey)+dep>T) return ;
    int l,r;
    for(int i=0;i<4;i++){
        l=x+dx[i];r=y+dy[i];

        if(l<1||r<1||l>n||r>m) continue;
        if(mp[l][r]=='*') continue;

        dfs(dep+1,l,r);
    }
}
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    cin>>sx>>sy>>ex>>ey;
    dfs(0,sx,sy);
    printf("%d\n",ans);
    return 0;
}

4、这样直接用欧式距离来判断的话，那我之前剪枝得到10分的那个应该也能通过，于是继续调试
100分代码

#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=1e2+10,mod=100003;
const int inf=0x3f3f3f3f;
struct E{
    int x,y,u;
};
int d[N][N];//记录到终点的最短距离
bool st[N][N];

char mp[N][N];
int n,m,ans;
int T;
int sx,sy,ex,ey;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void bfs(){//从终点搜索到其他所有点的最端距离
//如果在搜索的过程中发现，此时剩下的步数已经小于了最短距离，则一定不能到达
    memset(d,0x3f,sizeof(d));
    queue<E>q;
    q.push(E{ex,ey,0});
    d[ex][ey]=0;st[ex][ey]=1;
    E nw,nx;
    int x,y,u;
    int l,r;
    while(!q.empty()){
        nw=q.front();q.pop();
        x=nw.x;y=nw.y;u=nw.u;
        for(int i=0;i<4;i++){
            l=x+dx[i];r=y+dy[i];
            if(l<1||r<1||l>n||r>m) continue;
            if(mp[l][r]=='*'||st[l][r]==1) continue;
            st[l][r]=1;d[l][r]=u+1;
            q.push(E{l,r,u+1});
        }
    }
}
void dfs(int dep,int x,int y){
    //注意这个地方，有可能d[x][y]是相同的
    //if(d[x][y]+dep==T) {ans++;return ;}//新加的剪枝

    if(d[x][y]+dep>T) return ;
    //这一句我原本写的<，然后交了一发后发现是错误的，就给删除了
    //想不到我距离AC竟然那么近QAQ

    if(dep>T) return ;
    if(dep==T&&x==ex&&y==ey) {ans++;return;}
    int l,r;
    for(int i=0;i<4;i++){
        l=x+dx[i];r=y+dy[i];
        if(l<1||r<1||l>n||r>m) continue;
        if(mp[l][r]=='*') continue;
        dfs(dep+1,l,r);
    }
}
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    cin>>sx>>sy>>ex>>ey;
    bfs();
    dfs(0,sx,sy);
    printf("%d\n",ans);
    return 0;
}