Tempter of the Bone

暑假的时候，小明和朋友去迷宫中寻宝。然而，当他拿到宝贝时，迷宫开始剧烈震动，他感到地面正在下沉，他们意识到这是一个陷阱！他们想尽一切办法逃出去。

迷宫是一个大小为 N*M 的长方形，迷宫中有一扇门。一开始，门是关着的，他会在第 t 秒的时间打开。因为，小明和朋友必须在第 t 秒到大门口。每一秒，他都可以向上下左右四个方向移动一个点。一旦他移动了，他刚才所在的点就消失，（这意味着他不能回到他已经走过的点）。他不能在一个点上停留超过一秒，并且不能走障碍点。小明和朋友能安全的逃出吗？

Input

输入由多个测试用例组成。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局，每一行包含M个字符。下列字母分别表示：

“X”: 一堵墙，小明和朋友不能在上面停留

“S”: 起点

“D”: 门

“.”: 可以走的点

输入以 3 个 0 时结束。这个测试用例不需要处理。

Output

对于每组样例输出一行。

如果小明能够安全逃出，输出 “YES” ，否则输出 “NO”。

Sample Input

4 4 5

S.X.

…X.

…XD

…

3 4 5

S.X.

…X.

…D

0 0 0

Sample Output

NO

YES

题意不用多说，主要是理解减枝的思想，当遇到不满足条件的递归分枝时就返回，即减枝。

首先判断可走的点的数目是否大于要求的时间，如果小于等于就输出NO。

1.如果当前步数(step) >= T 而且还没有找到D点，则返回。

2.设当前位置(x, y)到D点(dx, dy)的最短距离为s，到达当前位置(x, y)已经花费时间(步数)step，那么，如果题目要求的时间T - step < s，则剪掉。

3. 对于当前位置(x, y)，如果，(T-step-s)是奇数，则剪掉(奇偶剪枝)。

减枝部分内容来自 https://blog.csdn.net/chyshnu/article/details/6171758

代码如下

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
int vis[15][15];
char map[15][15];
int n,m,t,flag=0,sx,sy,ex,ey;

int ad[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int x,int y,int step){
    if(flag) return;
    if(map[x][y]=='D' && step==t){
        flag=1;
        return;
    }
    if(step>=t) return;
    int s=abs(x-ex)+abs(y-ey);
    if(t-step<s) return;
    int dis=t-step-s;
    if(dis<0 || dis%2!=0) return;

    int dxx,dyy;
    for(int i=0;i<4;i++){
        dxx=x+ad[i][0];
        dyy=y+ad[i][1];
        if(dxx>=0 && dxx<n && dyy>=0 && dyy<m && map[dxx][dyy]!='X'&& vis[dxx][dyy]==0){
            vis[dxx][dyy]=1;
            dfs(dxx,dyy,step+1);
            vis[dxx][dyy]=0;
        }

    }

}
int main() {
    int xnumber=0;
    while(cin>>n>>m>>t,n+m+t){
        memset(vis,0, sizeof(vis));
        memset(map,0, sizeof(map));
        xnumber=0;
        getchar();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%c",&map[i][j]);
            }
            getchar();
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j]=='S'){
                    sx=i;
                    sy=j;
                    vis[i][j]=1;
                }else if(map[i][j]=='D')
                {
                    ex=i;
                    ey=j;
                }else if(map[i][j]=='X')
                {
                    xnumber++;
                }
            }
        }
        flag=0;
        if(n*m-xnumber>t){
            dfs(sx,sy,0);
        }
        if(flag){
            cout<<"YES"<<endl;
        } else cout<<"NO"<<endl;

    }
    return 0;
}