杭电1010 Tempter of the Bone （DFS+奇偶剪枝）

Problem Description
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

题目分析 ：这个题目很新奇，稍不容易就陷入死循环，导致程序运行时间变长，那就意味着如果这个题目按照以往的代码写那么就是超时，所以奇偶剪枝就因运而生。

在这里我简单的介绍一下奇偶剪枝的概念，就是在一个n * m的矩形里面，一共有n * m个点，每个点都有自己独特的坐标，我们把x，y坐标相加看其奇偶性，那么就可以发现，以一个点为例，如果想走到相同奇偶性的点那么一定要走偶数步数，如果走到不同奇偶性的点一定需要奇数步数，那么我们就可以根据上面所说，对其进剪枝操作。

奇偶剪枝的代码

 if (abs(sx - ex) + abs(sy - ey) > k || (ex + sx + ey + sy + k) % 2 == 1)
        {
   //奇偶剪枝
            puts("NO");
            continue;
        }

这个题目除了用到奇偶剪枝之外，其余操作就很平常，如果不用奇偶剪枝那么显然会超时，这是我第一次碰到奇偶剪枝的题目，所以目前的我还不知道什么时候需要用到奇偶剪枝，只能凭感觉，有的时候标记走过的点是很必要的，比如这个题目如果不标记起点那么就是超时，这和我们平常所见的搜索题有点不一样，像我之前的几篇博客写的bfs起点标记可加可不加，但是这样题目不加就超时，所以保持一个良好的习惯很有必要，另外，这个题目还需要用一个变量去标记是否在规定时间准时到达，如果到达，就直接return，感觉都不能多搜索了，因为不标记也是超时，所以这个题目在我无数次探索之后，发现，剪枝对这个题目来说就是精华所在，真的是步步剪枝！！！

另外这个题目让我自闭的一点竟然是大小写，一般的题目都是Yes，No，我没多想，就直接上手，结果这个题目竟然是YES，NO，我找了半天硬是没找出来，还是一个代码一个代码修改对照，最后还是给找出来了，这个故事告诉我们，读懂题题目还很有必要哦~减少不必要的麻烦和时间。

AC代码

#include <bits/stdc++.h>
using namespace std;
int d[4][2] = {
   -1, 0, 1, 0, 0, 1, 0, -1};
int sx, sy, ex, ey;
int vis[100][100];
char c[100][100];
int n, m, k, flag;
void dfs(int x, int y, int sum)
{
   
    if (flag)
        return;
    if (x == ex && y == ey && sum == k)
    {
   
        flag = 1;
        return;
    }
    if (sum > k)
        return;
    for (int i = 0; i < 4; ++i)
    {
   
        int xx = x + d[i][0];
        int yy = y + d[i][1];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && c[xx][yy] != 'X')
        {
   
            vis[xx][yy] = 1;
            dfs(xx, yy, sum + 1);
            vis[xx][yy] = 0;
        }
    }
}
int main()
{
   
    while (~scanf("%d%d%d", &n, &m, &k))
    {
   
        memset(vis, 0, sizeof(vis));
        flag = 0;
        if (n == 0 && m == 0 && k == 0)
            break;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            {
   
                scanf(" %c", &c[i][j]);
                if (c[i][j] == 'S')
                {
   
                    sx = i;
                    sy = j;
                }
                if (c[i][j] == 'D')
                {
   
                    ex = i;
                    ey = j;
                }
            }
        if (abs(sx - ex) + abs(sy - ey) > k || (ex + sx + ey + sy + k) % 2 == 1)
        {
   //奇偶剪枝
            puts("NO");
            continue;
        }
        vis[sx][sy] = 1;//标记改点已经走过
        dfs(sx, sy, 0);
        if (flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}