题解 P1535 【游荡的奶牛】

清风霁月 · 2018-07-29 10:14:31 · 题解

表示并不会什么记忆化搜索

（主要是本蒟蒻不喜欢三维数组）

于是我坚信，dfs一定能过，然而单纯的dfs一定过不了（数据那么坏）

好吧，那就只有剪枝了。。。代码应该很好懂

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,s,ans;
int sx,sy,tx,ty;
int map[200][200];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//四个方向
void dfs(int x,int y,int tot)
{
    if(tot>s) return;//时间超过了，没用
    if(x<1||x>n||y<1||y>m||map[x][y]) return;//越界了，走过了，没用
    if(abs(x-tx)+abs(y-ty)>s-tot) return;//距离太过遥远，肯定是走不到了，也没用
    if(x==tx && y==ty && s==tot)//到地点了，时间也刚刚好
    {
        ans++;//路径总数加1
        return;
    }
    dfs(x+1,y,tot+1);
    dfs(x-1,y,tot+1);
    dfs(x,y+1,tot+1);
    dfs(x,y-1,tot+1);//四个方向继续游荡吧
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char ss;
        cin>>ss;
        if(ss=='.')//标记有障碍的地方
        map[i][j]=0;
        else
        map[i][j]=1;
    }
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    dfs(sx,sy,0);
    cout<<ans;//输出
    return 0;//这是个好习惯
}