dfs+剪枝

Zhou_Wingay · 2020-11-01 21:37:27 · 题解

dfs：

利用 dfs 遍历来进行移动。

void dfs(int h,int l,int now){
    int i,d[4][2]={1,0,0,1,-1,0,0,-1};
    if(now==t+1&&h==r2&&l==c2){sum++;return;}
    else if(now==t+1)return;
    else{
        for(i=0;i<4;i++){
            int x,y;
            x=h+d[i][0];y=l+d[i][1];
            if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='.'){
                dfs(x,y,now+1);
            }
        }
    }
}

剪枝：

利用勾股定理求出当前点与终点的距离。

设当前点为 s1 终点为 s2。

则最短直线距离为：\sqrt{|h_{s1}-h_{s2}|^{2}+|l_{s1}-l_{s2}|^{2}}。

这个距离是在没有障碍物的情况下的直线距离（最短距离），如果剩下的时间连这样走都不够，那就根本没必要继续 dfs 了。

if(sqrt(abs(r2-x)*abs(r2-x)+abs(c2-y)*abs(c2-y))>t-now+1)continue;

最后就是完整代码了：

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
char a[105][105];
int r1,c1,r2,c2,sum;
void dfs(int h,int l,int now){
    int i,d[4][2]={1,0,0,1,-1,0,0,-1};
    if(now==t+1&&h==r2&&l==c2){sum++;return;}//如果按时到达，那么路径数加1
    else if(now==t+1){return;}
    else{
        for(i=0;i<4;i++){
            int x,y;
            x=h+d[i][0];y=l+d[i][1];
            if(sqrt(abs(r2-x)*abs(r2-x)+abs(c2-y)*abs(c2-y))>t-now+1)continue;//剪枝
            if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='.'){
                dfs(x,y,now+1);//继续深搜
            }
        }
    }
}
int main(){
    int i,j;
    cin>>n>>m>>t;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    cin>>r1>>c1>>r2>>c2;
    dfs(r1,c1,1);
    cout<<sum;
    return 0;
}