HDU 1010 Tempter of the Bone

奇偶剪枝

若 t-[abs(ex-sx)+abs(ey-sy)] 结果为非偶数(奇数)，则无法在t步恰好到达.

Description

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.

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

思路

恰好到达，不能用bfs，用dfs。另外dfs搜索量大要剪枝，另外dfs用不到结构体

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
///BFS要以（ 结构体 ）形式存数据
///DFS只要两点：当前点与终点（不需结构体）
int n, m, time, now_x, now_y, ex, ey, t;
bool vis[10][10];///可改图以省略（通路访问完毕改为墙）
char mp[10][10];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool flag;

///DFS无法中断，return返回的不知是哪一级，尽量不要在此函数里执行输出操作(易多次输出)
void dfs(int x, int y, int t)
{

    ///①检验部分
    if(mp[x][y] == 'D' && t == time)
    {
        flag = 1;
        return ;
    }

    ///②剪枝部分
    if(t >= time || flag)///超时剪枝 || 成功剪枝
        return ;
    if(abs(x - ex) + abs(y - ey) > time )///缺时剪枝
        return ;
    if(abs( time - t - abs(x - ex) - abs(y - ey) )% 2)///奇偶剪枝
        return ;

    ///③搜索部分
    for(int i = 0; i < 4; ++i)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(x >= n || x < 0 || y >= m || y < 0 || vis[xx][yy] || mp[xx][yy] == 'X' )
            continue;
        vis[xx][yy] = 1;
        dfs(xx, yy, t + 1);
        vis[xx][yy] = 0;///取消标记，另寻他路
    }
    return ;
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &time) && (n || m || t))
    {
        flag = 0;
        memset(vis, 0, sizeof(vis));///两个数组都要初始化
        memset(mp, 0, sizeof(mp));///我起初把初始化放在了读图的后面！

        ///读图
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", mp[i]);///或者cin读入
            for(int j = 0; j < m; ++j)
            {
                if(mp[i][j] == 'S')
                {
                    now_x = i;
                    now_y = j;
                }
                if(mp[i][j] == 'D')
                {
                    ex = i;
                    ey = j;
                }
            }
        }

        ///对起点的“剪枝”,相当于“刨根”吧
        if(abs(now_x - ex) + abs(now_y - ey) > time || abs(time -abs(now_x - ex) - abs(now_y - ey) ) & 1 )
        {
            cout << "NO" << '\n';
            continue;
        }

        vis[now_x][now_y] = 1;
        dfs(now_x, now_y, 0);
        if(flag)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
//        for(int i = 0; i < n; ++i)
//        {
//            for(int j = 0; j < m; ++j)
//                cout << mp[i][j];
//            cout << '\n';
//        }
    }
    return 0;
}