【HDU - 1010】Tempter of the Bone（dfs+剪枝）

时间：2022-08-10 14:58:22

Tempter of the Bone

直接上中文了

Descriptions:

暑假的时候，小明和朋友去迷宫中寻宝。然而，当他拿到宝贝时，迷宫开始剧烈震动，他感到地面正在下沉，他们意识到这是一个陷阱！他们想尽一切办法逃出去。
迷宫是一个大小为 N*M 的长方形，迷宫中有一扇门。一开始，门是关着的，他会在第 t 秒的时间打开。因为，小明和朋友必须在第 t 秒到大门口。每一秒，他都可以向上下左右四个方向移动一个点。一旦他移动了，他刚才所在的点就消失，（这意味着他不能回到他已经走过的点）。他不能在一个点上停留超过一秒，并且不能走障碍点。小明和朋友能安全的逃出吗？


Input

输入由多个测试用例组成。每个测试用例的第一行包含三个整数 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

题目链接：
https://vjudge.net/problem/HDU-1010

一开始没读清题 上去就bfs WA 了

然后想用bfs做，错了好多次发现不行，bfs更加适用于求最短路径等等最优化的题目由于这道题目时间给定，而到目的的所用却不一定。即：可能有多种到达目的地的方法，不同方法需要的时间不同。并不要求是最短时间。所以bfs不合适

比如：

4 5 5
X X S . .
X X . . X
X . . . X
X . D . X
从S到D其实有很多条路的，最短3步，也可以有其他很多走法，不同走法需要的时间不同，用bfs求的是最短时间，如果题目时间是5呢？BFS答案是错误的，但是其实可以走到的。

然后dfs 结果超时 需要剪枝

奇偶剪枝：

是数据结构的搜索中，剪枝的一种特殊小技巧。
现假设起点为(sx,sy)，终点为（ex,ey），给定t步恰好走到终点，
 
s        
|        
|        
|        
+ — — — e
 
 
如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；
 
　　
s — — —  
  — — +  
| +      
|        
+ — — — e
 
 
如图，为一般情况下非最短路径的任意走法举例，step2=14；
step2-step1=6，偏移路径为6，偶数（易证）；
故，若t-[abs(ex-sx)+abs(ey-sy)]结果为非偶数（奇数），则无法在t步恰好到达；
返回，false；
反之亦反。
具体操作见代码
AC代码
#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 10

using namespace std;

int T,n,m,steps;

int ex,ey,sx,sy;;

char mp[Maxn][Maxn];//原始地图

int vis[Maxn][Maxn];//记录人是否走过

int dt[][]= {{,},{-,},{,},{,-}};//四个方向

int dfs(int x,int y,int step)//当前坐标 当前步数

{

    if(x==ex&&y==ey&&step==steps)//满足条件，成功

        return ;

    for(int i=; i<; i++)//四个方向

    {

        int tx=x+dt[i][];

        int ty=y+dt[i][];

        if(tx>=&&tx<n&&ty>=&&ty<m&&!vis[tx][ty]&&mp[tx][ty]!='X')//判断条件

        {

            vis[tx][ty]=;

            if(dfs(tx,ty,step+))//继续搜索

                return ;

            vis[tx][ty]=;//回溯

        }

    }

    return ;

}

int main()

{

    while(cin>>n>>m>>steps,n+m+steps)

    {

        MEM(vis,);//初始化

        for(int i=; i<n; i++)

            for(int j=; j<m; j++)

            {

                cin>>mp[i][j];

                if(mp[i][j]=='S')//起点

                {

                    sx=i,sy=j;

                    vis[sx][sy]=;//标记

                }

                if(mp[i][j]=='D')//终点

                    ex=i,ey=j;

            }

        if((abs(ex-sx)+abs(ey-sy))%!=steps%)//剪枝，不然超时

            cout<<"NO"<<endl;

        else

        {

            if(dfs(sx,sy,))

                cout<<"YES"<<endl;

            else

                cout<<"NO"<<endl;

        }

    }

}

相关文章