Tempter of the Bone
直接上中文了
Descriptions:
暑假的时候，小明和朋友去迷宫中寻宝。然而，当他拿到宝贝时，迷宫开始剧烈震动，他感到地面正在下沉，他们意识到这是一个陷阱！他们想尽一切办法逃出去。
迷宫是一个大小为 N*M 的长方形，迷宫中有一扇门。一开始，门是关着的，他会在第 t 秒的时间打开。因为，小明和朋友必须在第 t 秒到大门口。每一秒，他都可以向上下左右四个方向移动一个点。一旦他移动了，他刚才所在的点就消失，（这意味着他不能回到他已经走过的点）。他不能在一个点上停留超过一秒，并且不能走障碍点。小明和朋友能安全的逃出吗？
Input
输入由多个测试用例组成。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局，每一行包含M个字符。下列字母分别表示：
输入以 3 个 0 时结束。这个测试用例不需要处理。
Output
对于每组样例输出一行。
如果小明能够安全逃出，输出 "YES" ，否则输出 "NO"。
Sample Input
Sample Output
题目链接：
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 结果超时 需要剪枝
奇偶剪枝：
| s | ||||
| | | ||||
| | | ||||
| | | ||||
| + | — | — | — | e |
| s | — | — | — | |
| — | — | + | ||
| | | + | |||
| | | ||||
| + | — | — | — | e |
#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;
}
}
}