一开始没仔细看题(英文渣)，一扫样例，这不广搜嘛，然后血崩。
认真翻译了一遍。然后用深搜写，然后在一个小错误上面卡了4个小时。。
终于AC了。。
其实个人感觉用广搜也不是不可以，只是超时。。
思路
递归函数：模拟每一步状态，递归函数开头写终止条件，然后更新坐标值，判断是否是墙或走过的路，然后把坐标代入下一层递归。
剪枝
1、这里的MinStep为曼哈顿距离“两点在南北方向上的距离加上在东西方向上的距离”，是本题中两点间的最短步数（时间）
如果MinStep比给定的T大，显然狗不能到达。abs()为返回绝对值函数
int MinStep = abs(endx-beginx) + abs(endy-beginy);
if(MinStep > t){
cout<<"NO"<<endl;
continue;
}
2、奇偶剪枝，详见百度百科“奇偶剪枝"
if( abs(t - MinStep) % 2 == 1){
cout<<"NO"<<endl;
continue;
}
3、 把效率提升10倍的很厉害的优化。。（原理：步数t和墙数wall的和一定比迷宫面积大）
if(n*m-wall <= t) //436ms->46ms
{
cout<<"NO" << endl;
continue;
}
下面贴上自己的渣翻译，虽然比机翻人性化一点。。
Problem Description
小狗在一个古老的迷宫找到了骨头，它很欢喜，当它捡起的时候，迷宫地动山摇。它意识到这是一个陷阱，它拼命的想走出这个迷宫，等待它的命运将是什么呢？
迷宫是长方形(N*M)。门为迷宫的出口。一开始门是关着的，它会在T秒时，短时间打开(小于1秒)。因此小狗必须准确的在T秒到达门处。
每秒小狗可以移动一个格子。每次它到达一个格子，这块格子会在下一秒下沉。它不能在一个格子停留超过1秒，也不能去已经访问过的格子。
小狗可以逃出生天吗？帮帮它。
Input
输入多组测试数据。第一行3个整数 N，M，T（1 < N, M < 7, 0 < T < 50 ）, 分别表示迷宫的宽、长、门打开的时间。接下来N行表示迷宫的布局，每行有M个字符。字符含义如下:
'X': 墙，小狗不能通过
'S': 起点
'D': 门
'.': 普通格子
'0 0 0'来终止输入
Output
每组数据用"YES"表示小狗可以存活，反之"NO"
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5�0AS.X.
..X.
...D
0 0 0
Sample Output
NO
YES
AcceptCode
/*
* created by zsdostar
* 2016/5/1
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int abs(int fx);
void dfs(int x,int y,int step);
char maze[51][51],book[51][51];
int endx,endy;
int n,m,t,flag,wall;
int main()
{
int beginx,beginy,step=0;
while(cin>>n>>m>>t)
{
if(n==0 && m==0) break;
flag = 0;wall = 0;
memset(book,0,sizeof(book));//mdzz，废了一下午时间在这上面。。结果原因是每次book没有初始化，导致下一组数据会读取上一组book代表的状态。。泪崩
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S') { beginx = i; beginy = j; }
else if(maze[i][j]=='D'){ endx = i; endy = j; }
else if(maze[i][j]=='X'){ wall++; book[i][j] = 1; }
}
}
if(n*m-wall <= t)//436ms->46ms
{
cout<<"NO"<<endl;
continue;
}
int MinStep = abs(endx-beginx) + abs(endy-beginy);
if(MinStep > t){
cout<<"NO"<<endl;
continue;
}
if( abs(t - MinStep) % 2 == 1){
cout<<"NO"<<endl;
continue;
}
book[beginx][beginy]=1;
dfs(beginx,beginy,step);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
int abs(int fx)
{
if(fx<0)
fx=-fx;
return fx;
}
void dfs(int x,int y,int step)
{
if(x<0||x>=n||y<0||y>=m)//数组边界检测
{
return;
}
int next[4][2]{{0,1},{1,0},{0,-1},{-1,0}};//上下左右
if(x==endx && y==endy)
{
if(step==t)
flag=1;
}
if(flag)
return;
int tx,ty,k;
for(k=0;k<=3;k++)//遍历上下左右
{
tx = x + next[k][0];
ty = y + next[k][1];
if(book[tx][ty] == 0)//如果不撞墙，不是已走过的路，就进入更深层的dfs()
{
book[tx][ty] = 1;
dfs(tx,ty,step+1);
book[tx][ty] = 0;
if(flag)
return;
}
}
return;
}
谨慎谨慎再谨慎。。不然错误找出来简直发现自己智障。。
再吐槽新版编辑器，bug好多。。
网友评论