HDU1010 --- Tempter of the Bone（dfs+剪枝）

佚名 4年前 (2020-01-28) 算法 2222人围观抢沙发百度已收录

小明做了一个很久很久的梦，醒来后他竟发现自己和朋友在一个摇摇欲坠的大棋盘上，他们必须得想尽一切办法逃离这里。
经过长时间的打探，小明发现，自己所在的棋盘格子上有个机关，上面写着“你只有一次机会，出发后t秒大门会为你敞开”，而他自己所在的棋盘是大小为 N*M 的长方形，他可以向上下左右四个方向移动（不可走有障碍点）。棋盘中有一扇门。根据机关的提示，小明顿时明白了，他和朋友必须在第 t 秒到门口。而这一切，没有回头路！因为一旦他移动了，他刚才所在的点就会消失，并且他不能在一个点上停留超过一秒，不然格子会爆炸。大逃亡开始了，请问小明和朋友能安全的逃出这奇怪的棋盘吗？

Input

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入多组测试数据。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分别表示棋盘的大小和门打开的时间。接下来的N行给出棋盘布局，每一行包含M个字符。其中
".": 无障碍点
"X": 障碍点
"S": 起点
"D": 门

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

代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main{
        static int n,m,T;
        static final int N=10;
        static int sx,sy,ex,ey;
        static int dx[]={0,0,1,-1};
        static int dy[]={1,-1,0,0};
        static char map[][]=new char[N][N];
        static boolean vis[][]=new boolean[N][N];
        static boolean flag;
        
        static void dfs(int x,int y,int t){
　　　　　　　　　　//这种多if判断的一定加上return if(flag) return; //已经找到一种走法 if(t>T)  return; //大于要求的时间 if(T-t-Math.abs(x-ex)-Math.abs(y-ey)<0) return; //剩余的步数不足以到达终点
                if((T-t)%2!=(Math.abs(x-ex)+Math.abs(y-ey))%2) return; //奇偶性一致
                if(t==T && x==ex && y==ey){
                         flag=true;
                }
                
                for(int i=0;i<4;i++){
                        int xx=x+dx[i];
                        int yy=y+dy[i];
                        if(xx<0 || yy<0 || xx>=n || yy>=m ||vis[xx][yy]) continue;
                        vis[xx][yy]=true;
                        dfs(xx,yy,t+1);
                        vis[xx][yy]=false;
                }
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                while(scan.hasNext()){
                        n=scan.nextInt();
                        m=scan.nextInt();
                        T=scan.nextInt();
                        if(n==0 && m==0 &&T==0) break;
                        for(int i=0;i<n;i++) map[i]=scan.next().toCharArray();
                        for(int i=0;i<N;i++)  Arrays.fill(vis[i],false);
                        for(int i=0;i<n;i++)
                            for(int j=0;j<m;j++)
                                if(map[i][j]=='S'){
                                        sx=i; sy=j;
                                }
                                else if(map[i][j]=='D'){
                                        ex=i; ey=j;
                                }
                                else if(map[i][j]=='X') 
                                        vis[i][j]=true;
                        vis[sx][sy]=true;
                        flag=false;
                        dfs(sx,sy,0);
                        if(flag) System.out.println("YES");
                        else System.out.println("NO");
                }
        }
}