DFS剪枝初步

剪枝经典例题：

Tempter of the Bone http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目描述： 一个迷宫有N*M格，有一些格子是地板能走，有一些格子是障碍不能走。给一个起点S和一个终点D。一只小狗从S出发，每步走一块地板，在每个地板不能停留，而且走过的地板都不能再走。给定一个T，问小狗能正好走T步到达D吗？

输入输出：有很多测试样例，每个测试中，第1行是整数N，M，T， 1 < N, M < 7, 0 < T < 50。后面有N行，每行M个字符，有这些字符：‘X’: 墙；‘S’: 起点；‘D’: 终点；’.’: 地板。最后一行是’0 0 0’，表示结束。如果狗能逃出，输出YES，否则输出NO。

输入输出样例：

输入

4 4 5

S.X.

…X.

…XD

…

3 4 5

S.X.

…X.

…D

0 0 0

输出

NO

YES。

题解：对于路径问题应该用DFS，对于这题采用奇偶剪枝。

曼哈顿距离f=abs(c−x)+abs(d−y)，如果S和D的曼哈顿距离f是奇数，说明S和D一个是0一个是1；如果f是偶数，说明S和D同0或同1。对于此题，如果T−f是奇数则肯定无解，因为T和f必须同奇或同偶。

代码：

#include <bits/stdc++.h>
using namespace std;
char mat[8][8],visit[8][8];
int n, m, t;
int flag;           //flag=1，表示找到了答案
int a, b, c, d;     //起点S(a,b)，终点D(c,d)
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};        //上下左右4个方向
#define CHECK(xx,yy) (xx>=0 && xx<n && yy>=0 && yy<m)  //是否在迷宫中

void dfs(int x, int y, int time){     
    if(flag)  return;                   //逐层退出DFS，有多少层DFS，就退多少次
    
    if(mat[x][y] == 'D'){        
        if(time == t)    flag = 1;      //找到答案
        return;                         //D只能走一次，所以不管对不对，都返回   
    }    
    //if(time > t)     return;          //剪枝(1)：因为有剪枝(2)，(1)就多余了

    int tmp = t - time - abs(c-x) - abs(d-y);
    if(tmp < 0)     return;             //剪枝（2）
    
    for(int i=0; i<4; i++){             //上下左右
        int xx = x + dir[i][0], yy = y + dir[i][1];
        if(CHECK(xx,yy)  && mat[xx][yy]!='X' && !visit[xx][yy]){      
            visit[xx][yy] = 1;          //地板标记为走过，不能再走        
            dfs(xx, yy, time + 1);      //遍历所有的路径
            visit[xx][yy] = 0;          //递归返回，这块地板恢复为没走过
        }
    }    
    return;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&t)){
        if(n==0 && m==0 && t==0)    break;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                cin>>mat[i][j];
                if(mat[i][j] == 'S') a=i,b=j;
                if(mat[i][j] == 'D') c=i,d=j;
            }
        memset(visit, 0, sizeof(visit));
        int tmp = t - abs(c-a) - abs(d-b);  //在DFS之前，做奇偶判断
        if(tmp & 1){                        //无解，不用DFS了
            puts("NO"); 
            continue;
        }
        flag = 0;
        visit[a][b] = 1;                    //标记起点已经走过
        dfs(a, b, 0);                       //搜索路径
        
        if(flag) puts("YES");
        else     puts("NO");
    }
    return 0;
}