HDU-1010 奇偶性剪枝+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 x m大小的迷宫。其中字符’S’表示起点，字符’D’表示出口，字符’x’表示墙壁，字符，. '表示平地。你需要从’S’出发走到’D’，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。

每次移动消耗1时间，走过路都会塌陷，因此不能走回头路或者原地不动。现在已知出口的大门会在T时间打开，判断在0时间从起点出发能否逃离迷宫。

如上图所示，将n X m的网格染成黑白两色。我们记每个格子的行数和列数之和为x,如果x为偶数，那么格子就是白色，反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论是:走奇数步会改变颜色，走偶数步颜色不变。

那么如果起点和终点的颜色一样，而T是奇数的话，就不可能逃离迷宫。同理，如果起点和终点的颜色不一样，而T是偶数的话，也不能逃离迷宫。遇到这两种情况时，就不用进行DFS了，直接输出"NO"。

这样的剪枝就是奇偶性剪枝，本质上也属于可行性剪枝。

#include"iostream"
#include"cstdio"
#include"cmath"
#include"cstring"
#include"cstdlib"
#include"cctype"
#include"vector"
#include"stack"
#include"queue"
#include"map"
#include"algorithm"
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lowbit(x) x&-x
#define ll long long
const double PI=acos(-1.0);
using namespace std;
const int mod = 998244353 ;
const int M = 10 + 10;
const int limt = 1<<20;
const int INF = 1e9;

bool flag;
char mp[M][M];
int t,n,m,di,dj;
int dir[4][2]= {
   0,-1,0,1,1,0,-1,0};

void dfs(int cnt,int si,int sj)
{
   
    int i,tmp;
    if(si>n||sj>m||si<=0||sj<=0) return;
    if(cnt==t&&si==di&&sj==dj) flag=1;
    if(flag) return;

    tmp=(t-cnt)-abs(si-di)-abs(sj-dj);//曼哈顿距离与时间的差值
    if(tmp<0||tmp&1) return;//tmp&1是奇偶性剪枝
    for(i=0; i<4; i++)
    {
   
        if(mp[si+dir[i][0]][sj+dir[i][1]]!='X')
        {
   
            mp[si+dir[i][0]][sj+dir[i][1]]='X';
            dfs(cnt+1,si+dir[i][0],sj+dir[i][1]);
            mp[si+dir[i][0]][sj+dir[i][1]]='.';
        }
    }
    return;
}

int main()
{
   
    int x,y;
    while(~scanf("%d%d%d",&n,&m,&t))
    {
   
        int wall=0;
        if(n==0&&m==0&&t==0)
            break;

        for(int i=1; i<=n; i++)
        {
   
            for(int j=1; j<=m; j++)
            {
   
                scanf(" %c",&mp[i][j]);
                if(mp[i][j]=='S')
                {
   
                    x=i;
                    y=j;
                }
                else if(mp[i][j]=='D')
                {
   
                    di=i;
                    dj=j;
                }
                else if(mp[i][j]=='X') wall++;
            }
        }
        if(n*m-wall<=t)//时间大于可走的步树
        {
   
            cout<<"NO"<<endl;
            continue;
        }
        flag=0;
        mp[x][y]='X';
        dfs(0,x,y);
        if(flag)
            cout<<"YES"<<endl;
        else   cout<<"NO"<<endl;
    }

    return 0;
}