【HDU 1010】顺序刷题 Tempter of the Bone （dfs 奇偶剪枝）

题目大意

给出一张 $n*m$n∗m 的图，图中标有起始点 $S$S，终点 $D$D，和不能走的墙 $X$X。问是否可以恰好走 k 步 从起点走到终点（不能走重复的点）。

---

解题思路

一开始以为是 bfs，但是这个就算地图状态可以状压，状态数也还是太多了，所以广搜明显是不行的。

后来转到 dfs， 考虑剪枝。最基础的可行性剪枝 -> 如果现在剩余的可走步数已经严格小于当前位置和终点位置的曼哈顿距离，则剪掉，不过这个剪枝的效果并不够好。稍微进阶一点的可行性剪枝 -> 从网格上一个点到另一个点的所有可行路径的长度的奇偶性，与这两点间曼哈顿距离的奇偶性，两者必定相同。利用这个性质进行剪枝，效果还够用，随便写写就可以了。

---

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn=11, dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,k,dx,dy;
char Map[maxn][maxn];

int dis(int x,int y) {
    return abs(x-dx)+abs(y-dy);
}
bool in_range(int x,int y) {
    if(Map[x][y]=='X') return false;
    if(x<0 || x>=n || y<0 || y>=m) return false;
    return true;
}

int dfs(int x,int y,int step) {
    if(Map[x][y]=='D') return (step==k);
    if((k-step)<dis(x,y)) return false;
    if((k-step)%2!=dis(x,y)%2) return false;
    Map[x][y]='X';
    int nx,ny,i;
    for(i=0;i<4;++i) {
        nx=x+dir[i][0], ny=y+dir[i][1];
        if(!in_range(nx,ny)) continue;
        if(dfs(nx,ny,step+1)) return true;
    }
    Map[x][y]='.';
    return false;
}

void work() {
    register int i,j;
    for(i=0;i<n;++i) scanf("%s",Map[i]);

    int sx=EOF, sy=EOF;
    for(i=0;i<n;++i)
    for(j=0;j<m;++j) {
        if(Map[i][j]=='D') dx=i, dy=j;
        if(Map[i][j]=='S') sx=i, sy=j;
    }

    if(dfs(sx,sy,0)) printf("YES\n");
    else printf("NO\n");

    return;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input0.txt","r",stdin);
#endif // ONLINE_JUDGE
    while(scanf("%d%d%d",&n,&m,&k)) {
        if(!n && !m && !k) break;
        work();
    }

    return 0;
}