HDOJ-1010 Tempter of the Bone

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目大意

小狗要逃离一个$N×M$的长方形迷宫，迷宫出口的门仅在第 $T$ 秒时开一瞬间（不到1秒）。因此，小狗必须恰好在第 $T$ 秒到达门口才能逃离。 每一秒，它可以向上下左右任意移动一格，且所有格子至多走一次。

Input

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

• X：无法通过的一堵墙
• S：起点
• D：出口的门
• .：可走的方块

输入以三个 $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

Solution

一道很明显的dfs题，因为题目存在恰好走 $T$ 步的限制，因此定义状态为$(x, y, step)$即可。进入下一层递归前，标记上一个位置不可访问，并在回溯时恢复，也是比较基本的dfs搜索思想。

一开始交了一发，虽然AC了，但耗时468ms，对这个耗时不是很满意，于是想了想可行的剪枝方式。

• 因为所有方格至多走一次，因此如果 $T >= N*M-wall$ ( $wall$ 是墙的数量)，直接输出 $NO$
• 奇偶性剪枝：如果起点到终点的曼哈顿距离与 $T$ 的奇偶性不一致，直接输出 $NO$ （因为绕路不改变奇偶性，就算能重复走之前的路也不改变奇偶性）
• 如果时间太短(t<abs(sx-ex)+abs(sy-ey)-2)，直接输出 $NO$

有了前两个剪枝之后，可以优化到109ms。第三个剪枝效果不大，推测应该是这样的样例比较少。

#include <bits/stdc++.h>
using namespace std;
const int N = 8;
int n,m,t,sx,sy,ex,ey;
char mp[N][N];
bool tag;
int nxt[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int x,int y,int step){
    if(tag || step>t) return;
    if(x==ex&&y==ey&&step==t){
        tag= true;
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+nxt[i][0];
        int ny=y+nxt[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m && mp[nx][ny]!='X'){
            mp[nx][ny]='X';
            dfs(nx,ny,step+1);
            mp[nx][ny]='.';
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    while (cin>>n>>m>>t,n||m||t){
        int wall=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='X') ++wall;
                else if(mp[i][j]=='S') sx=i,sy=j;
                else if(mp[i][j]=='D') ex=i,ey=j;
            }
        }
        if(n*m-wall<=t){
            cout<<"NO\n";
            continue;
        }
        if((abs(sx+sy-ex-ey)&1)!=(t&1)){
            cout<<"NO\n";
            continue;
        }
        if (t<abs(sx-ex)+abs(sy-ey)-2) {
            cout<<"NO\n";
            continue;
        }
        tag=false;
        mp[sx][sy]='X';
        dfs(sx,sy,0);
        cout<<(tag?"YES":"NO")<<'\n';
    }
}