HDU 1010 —— Tempter of the Bone DFS+剪枝

原題：http://acm.hdu.edu.cn/showproblem.php?pid=1010php

題意：從S走到D，其中X是牆，不能走；給定時間 t ，問可否從S到D正好花費 t 時間（一步即爲一秒）；c++

思路：用DFS+剪枝；spa

此處有兩種剪枝：code

一、從S到D的最短期是 tmp = abs(sx-dx)+abs(sy-dy)，若是 tmp > t，顯然是「NO」；ci

二、若是 tmp <= t，那麼咱們要走到D就要往回走幾步，若是你往左多走了一步，那麼勢必就要往右也走一步，才能又回到D；因此剩餘步數 cnt = t - tmp 就必定是偶數；get

上述的第2種剪枝方法叫作「奇偶性剪枝」；string

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
int n, m, t;
string Map[maxn];
int sx, sy, dx, dy;
bool flag;
bool vis[maxn][maxn];

void DFS(int x, int y, int step){
    if(x < 0 || x >= n || y < 0 || y >= m)   return;
    if(x == dx && y == dy){
        if(step == t)   flag = true;
        return;
    }
    if(x-1 >= 0 && Map[x-1][y] != 'X' && !vis[x-1][y]){
        vis[x-1][y] = true;
        DFS(x-1, y, step+1);
        vis[x-1][y] = false;
    }
    if(flag)    return;
    if(Map[x+1][y] != 'X' && x+1 < n && !vis[x+1][y]){
        vis[x+1][y] = true;
        DFS(x+1, y, step+1);
        vis[x+1][y] = false;
    }
    if(flag)    return;
    if(y-1 >= 0 && Map[x][y-1] != 'X' && !vis[x][y-1]){
        vis[x][y-1] = true;
        DFS(x, y-1, step+1);
        vis[x][y-1] = false;
    }
    if(flag)    return;
    if(Map[x][y+1] != 'X' && y+1 < m && !vis[x][y+1]){
        vis[x][y+1] = true;
        DFS(x, y+1, step+1);
        vis[x][y+1] = false;
    }
    return;
}

int main(){
    while(cin>>n>>m>>t){
        memset(vis, false, sizeof vis);
        if(n == 0 && m == 0 && t == 0)  break;
        for(int i = 0;i<n;i++){
            cin>>Map[i];
            for(int j = 0;j<m;j++){
                if(Map[i][j] == 'S')    sx = i, sy = j;
                if(Map[i][j] == 'D')    dx = i,  dy = j;
            }
        }
        int tmp = abs(sx-dx)+abs(sy-dy);
        if(tmp > t || (t-tmp) % 2 != 0){
            cout<<"NO"<<endl;
            continue;
        }
        flag = false;
        vis[sx][sy] = true;
        DFS(sx, sy, 0);
        if(flag)    cout<<"YES"<<endl;
        else    cout<<"NO"<<endl;
    }
    return 0;
}