【杭电】[1010]Tempter of the Bone

问题描述

Tempter of the Bone

问题分析

给出一幅地图
问能不能在第T秒到达出口
因为并不是找最短距离，所以需要多次递归
而因为递归次数巨大
所以需要进行剪枝
比较好的剪枝思路有

如果已经有满足条件的，则其余递归都可以停止
记录总可走’.‘如果tcnt+1<T则肯定不行
最重要的根据曼哈顿距离（从一个点到达另外一个点的最短路径长度|x1-x2|+|y1-y2|）进行剪枝，路径长度(非最短)与最短路径的长度同奇偶,它们的差一定是偶数。所以判断当前位置到终点的曼哈顿距离与它到终点如果成立所需要的路径长度的奇偶性，如果它们的差是奇数则可以停止递归。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
int move[4]= {1,-1,0,0};
char map[10][10];
int cnt[10][10];
int H,W,T;
int sH,sW,eH,eW,se;
bool win;
int abs(int m) {
    return m>0?m:-m;
}
void dfs(int n,int m) {
    if(win)
        return ;
    int t=(T-cnt[n][m])-(abs(n-eH)+abs(m-eW));
    if(t<0||t&1)
        return ;
    if(n==eH&&m==eW&&cnt[n][m]==T)
        win=true;
    for(int i=0; i<4; i++) {
        int tn=n+move[i],tm=m+move[(i+2)%4];
        if(tn>=0&&tn<H&&tm>=0&&tm<W&&map[tn][tm]!='X'&&cnt[tn][tm]>cnt[n][m]+1&&cnt[n][m]<T) {
            cnt[tn][tm]=cnt[n][m]+1;
            dfs(tn,tm);
            cnt[tn][tm]=99999999;
        }
    }
}
int main() {
    while(scanf("%d %d %d",&H,&W,&T),H||W||T) {
        getchar();
        int tcnt=0;
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                cnt[i][j]=99999999;
                map[i][j]=getchar();
                if(map[i][j]=='S')
                    sH=i,sW=j;
                else if(map[i][j]=='D')
                    eH=i,eW=j;
                else if(map[i][j]=='.')
                    tcnt++;
            }
            getchar();
        }
        if(tcnt+1<T) {
            printf("NO\n");
            continue;
        }
        se=abs(sH-eH)+abs(sW-eW);
        win=false;
        cnt[sH][sW]=0;
        dfs(sH,sW);
        printf("%s\n",win?"YES":"NO");
    }
    return 0;
}