The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. 

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. 

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following: 

'X': a block of wall, which the doggie cannot enter; 
'S': the start point of the doggie; 
'D': the Door; or 
'.': an empty block. 

The input is terminated with three 0's. This test case is not to be processed. 

Output

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. 

Sample Input

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

Sample Output

NO
YES

这题如果不用剪枝结果会tle,先了解下剪枝，狗移动的步数必须等于t，之前以为到达目的地的时间可以小于t，然后错了好多次

所以每次dfs递归传参的时候参数必须有狗此时的坐标dog_x,dog_y,还有此时已经走过的步数step，每递归一遍step就加一

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
char map[10][10];
int vis[10][10];
int m,n,flag,t,dog_x,dog_y,door_x,door_y;
int _xy[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int dog_x,int dog_y,int step)
{
    if(flag)
        return ;
    if(dog_x==door_x&&dog_y==door_y&&step==t)
    {
        flag=1;
        return ;
    }
    int tem=t-step-abs(dog_x-door_x)-abs(dog_y-door_y);
    if(tem<0||tem&1)
        return ;
    for(int i=0; i<4; i++)
    {
        int x=dog_x+_xy[i][0];
        int y=dog_y+_xy[i][1];
        if(x<=0||x>m||y<=0||y>n)
            continue;
        if(!vis[x][y]&&map[x][y]!='X')
        {
            vis[x][y]=1;
            dfs(x,y,step+1);
            if(flag)
                return ;
            vis[x][y]=0;
        }
    }
    return ;
}
int main()
{
    while(scanf("%d%d%d",&m,&n,&t)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        int cnt=0;
        flag=0;
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='S')
                {
                    dog_x=i;
                    dog_y=j;
                }
                if(map[i][j]=='D')
                {
                    door_x=i;
                    door_y=j;
                }
                if(map[i][j]=='X')
                    cnt++;
            }
        }
        vis[dog_x][dog_y]=1;
        dfs(dog_x,dog_y,0);
        if(t>m*n-cnt-1)
        {
            printf("NO\n");
            continue;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

 

一：剪枝策略的寻找的方法

 

1）微观方法：从问题本身出发，发现剪枝条件

2）宏观方法：从整体出发，发现剪枝条件。

3）注意提高效率，这是关键，最重要的。

总之，剪枝策略，属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。

二：剪枝算法(算法优化)

 

1、简介

    在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

2、剪枝优化三原则: 正确、准确、高效.原则

     搜索算法,绝大部分需要用到剪枝.然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍. 在设计判断方法的时候,需要遵循一定的原则.

剪枝的原则

  1） 正确性

  正如上文所述,枝条不是爱剪就能剪的. 如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义. 所以,剪枝的前提是一定要保证不丢失正确的结果.

  2）准确性

  在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的. 可以说,剪枝的准确性,是衡量一个优化算法好坏的标准.

 3）高效性

设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的. 倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了.

 

3、分类

   剪枝算法按照其判断思路可大致分成两类:可行性剪枝及最优性剪枝.

3.1 可行性剪枝 —— 该方法判断继续搜索能否得出答案，如果不能直接回溯。

3.2 最优性剪枝

    最优性剪枝，又称为上下界剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。