描述 Description
绵羊爸爸一晚做了一个奇怪的梦，他梦见了萌萌十七岁的时候参加高考。萌萌所在的考点十分奇特，只有在规定的那1秒钟时刻才会开放(也就是说恰好到达考点，超过或时间未到都不能进入考点)。而萌萌从家里(萌萌的家在左上角)出去，在参加考试的途中可以在大街上走走(可以往上下左右任意方向走，不可以重复经过同一区域)，但不能去娱乐场所。现在给你一张JS市的地图，以及从萌萌离开家到考点开放的时间，请你预测萌萌在绵羊老师的梦中能否成功参加这次神奇的高考?
输入格式 Input Format
输入数据包含多个测试点（不超过5个）。
每个测试点的第一行包含三个正整数N,M,Time(0 < N,M <7; 0<Time<50)。接下来N行给出从萌萌家到考点的地图，每行包含M个字符。
所有字符中仅会出现以下情况：
'*'：表示普通道路
'D'：表示当地的考点(仅会出现一次)
'H'：表示娱乐场所；
文件将以0 0 0作为结束。
左上角的方格内字符一定为'*'。注意：出发点一开始不算走过。
输出格式 Output Format
对于每一个测试点，你只需要输出'Yes'表示可以准时到达，反之则输出'No'。
样例输入 Sample Input
4 3 4
S**
*H*
*HD
*H*
3 5 5
S*H**
H****
D****
0 0 0
样例输出 Sample Output
Yes
No
来源 Source
2009年江中信奥模拟赛
分析：
DFS搜索题。不过需要加上4个优化就可轻松的AC啦。
优化：
1.对于所有能走的统计一下，如果比规定时间小则无法到达。
2.对于最短路径(即：ex+ey-2如果比规定时间大则无法到达(ex,ey为终点左边))。
3.奇偶剪枝法：对于(ex,ey)如果(ex+ey)%2!=time%2则无法到达。
4.极限性剪枝(参考他人)：对于每个达到的点(i,j)如果加上从此点去到(ex,ey)的最短步数比time大则无法达到。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int dx[4]={0,-1,0,1};
const int dy[4]={1,0,-1,0};
bool map[10][10];
int n,m,ts,ex,ey,sum;
bool bk;
bool check(int x,int y)
{
if (x>0 && x<=n && y>0 && y<=m) return true;
return false;
}
void dfs(int x,int y,int t)
{
if (bk) return ;
if (abs(ex+ey-x-y)>t) return ;
if (x==ex && y==ey && t!=0) return ;
if (x==ex && y==ey && t==0)
{
bk=true; return ;
}
int tx,ty;
for (int i=0;i<=3;i++)
{
tx=x+dx[i]; ty=y+dy[i];
if (check(tx,ty) && map[tx][ty])
{
map[tx][ty]=false;
dfs(tx,ty,t-1);
map[tx][ty]=true;
}
}
}
int main()
{
while (scanf("%d%d%d",&n,&m,&ts))
{
if (n+m+ts==0) break;
getchar();
memset(map,false,sizeof(map));
char ch;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
scanf("%c",&ch);
if (ch!='H')
{
sum++; map[i][j]=true;
}
if (ch=='D')
{
ex=i; ey=j;
}
}
getchar();
}
bk=false;
if (sum>=ts && (ex+ey-2)<=ts && (ex+ey)%2==ts%2)
dfs(1,1,ts);
if (bk) printf("Yes\n");
else printf("No\n");
}
return 0;
}