题解 P1535 【游荡的奶牛】

maorui_cow · 2018-10-07 22:41:44 · 题解

这道题用dfs做可以过，但是坑很多。。。

1.必须恰好等于时间

2.这题可以走重复路径（意识到这个你已经很强啦）

3.但是性能很慢

所以，我优化啦！！！

假设下图中1为障碍，0为可走路，p为当前点

b 0 0 0 0

1 1 0 1 1

0 0 p 0 0

0 0 1 0 e

我们知道，p点到e点的最短距离（忽略障碍）为abs(px-ex)+abs(py-ey)

所以如果此路径都不能再规定时间内到达，就不用走啦！！！

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int a[105][105];
int xf[10],yf[10];
int ans=0;
int d[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};//万恶的方向矢量
void dfs(int x,int y,int bs)
{
    if(bs>s)//如果不是大于规定时间了，直接返回
    {
        return;
    }
    if(bs+(abs(x-xf[2])+abs(y-yf[2]))>s)//这里注意了，是关键优化点
    {
        return;
    }
    if(x==xf[2]&&y==yf[2]&&bs==s)//若满足条件
    {
        ans++;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int xx=x+d[i][0];
        int yy=y+d[i][1];
        if(a[xx][yy]==1)//不要写标记！！！
        {
            dfs(xx,yy,bs+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 c;
            cin>>c;
            a[i][j]=(c=='.'?1:0);//这里我非常方便的不要写出界函数
        }
    }
    scanf("%d%d%d%d",&xf[1],&yf[1],&xf[2],&yf[2]);
    dfs(xf[1],yf[1],0);
    printf("%d\n",ans);
    return 0;
}

AC啦！！！