DFS。有一条狗走迷宫,需要在时间T内走出迷宫。N,M为迷宫的大小。直接DFS会超时,得剪枝,神奇的剪枝之后就不会TLE了,而且不同的剪枝优化的时间效率是不一样的,我主要参考了两个,虽然效率都不是很高,但是容易理解吧。


        第一种:直接外层判断,我们可以把地图按照0、1编号。

0 1 0 1 0 1 

1 0 1 0 1 0 

0 1 0 1 0 1 

1 0 1 0 1 0 

        我们可以看出从0->1或者1->0需要奇数步,从1-1或者0->0需要偶数步。

        这样我们把开始的坐标(sx,sy)加一下得到s = sx+sy,终点坐标(ex,ey)加一下得到e = ex+ey。想一想,如果s和e标记相同那么它们相加是不是一个偶数?他们是偶数,那么时间是不是也得是偶数?如果s和e标记不同那么它们相加是不是一个奇数?他们是奇数那么时间是不是也得是奇数?这样一看我们就可以知道他们相加必须的是偶数才能进行Dfs搜索,于是有:

if((sx+sy+ex+ey+t)%2==0)Dfs(sx,sy,0);

        第二种:在Dfs过程中进行判断,判断原理也和第一种大致相同。

        我们考虑  剩余的时间:st = t-cur, 理论剩余步数,sg = abs(ex-x)+abs(ey-y),那么如果剩余的时间小于步数肯定是走不出去的,而如果要走出去,剩余的步数和时间都得具有相同的0、1标志,又:奇数-奇数=偶数、偶数-偶数=偶数。所以可得:

if(temp<0||temp%2)return;

Tips:通过两个DFS题目还领悟到一点,循环变量尽量还是不要设置为全局比较好,除非多次使用。

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1010


代码:

Memory: 1780 KB
Time: 312 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int n, m, t, i, j, sx,sy,ex,ey, flag;
int go[4][2]={-1,0,0,-1,0,1,1,0};    //这个搜索顺序也会影响时间我也是醉了,这个顺序是时间最快的
const int maxn=10;
char omap[maxn][maxn];
void Init()
{
    flag=0;
    for(i=0;i<maxn;i++)for(j=0;j<maxn;j++)omap[i][j]='X';
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)
    {
        cin>>omap[i][j];
        switch(omap[i][j])
        {
        case 'S':
            omap[i][j]='X';
            sx=i;
            sy=j;
            break;
        case 'D':
            omap[i][j]='.';
            ex=i;
            ey=j;
            break;
        case '.':
            omap[i][j]='.';
            break;
        }
    }
}
void Dfs(int x, int y, int cur)
{
    if(x==ex && y==ey && cur==t){flag=1;return;}
    //int temp=(t-cur)-(abs(ex-x)+abs(ey-y));
    //当前剩余时间-当前剩余步数
    //if(temp<0||temp%2)return;
    for(int k=0;k<4;k++)
    {
        int tx=x+go[k][0];
        int ty=y+go[k][1];
        if(omap[tx][ty]!='X')
        {
            omap[tx][ty]='X';
            Dfs(tx, ty, cur+1);
            if(flag)return;
            omap[tx][ty]='.';
        }
    }
    return;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(~scanf("%d%d%d", &n,&m,&t) && n+m+t)
    {
        Init();
        if((sx+sy+ex+ey+t)%2==0)Dfs(sx,sy,0);
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}