hdu---1010 Tempter of the Bone （经典DFS，注意剪枝）

古城微笑少年丶 2022-08-27 13:49 92阅读 0赞

/\*经典的dfs 主要考虑剪枝否则会超时  
HDU 1010  
\*/  
\# include<iostream>  
\# include<cstdio>  
\# include<cmath>  
\# include<cstdlib>  
\# include<cstring>  
\# include<string>  
using namespace std;  
char map\[10\]\[10\];//定义一个二维数组作为迷宫的地图  
bool flag\[10\]\[10\];//标记每一个位置的道路是否通顺的情况  
int n,m,t;  
int sx,sy;//定义起点作标  
int dx,dy;//定义终点坐标  
int block;//计算障碍物的个数  
int ans;//做标记，如果为真，则找到了符合条件的情况输出YES，否则为NO  
void dfs(int sx,int sy,int kt)  
\{  
if(sx<=0||sx>n||sy<=0||sy>m)//如果碰到墙，或越界则结束该函数  
return ;  
if(sx==dx&&sy==dy&&kt==t)//如果终点坐标等于起点的作标，且时间符合条件，则ns为真  
\{  
ans=1;  
return ;  
\}  
int time=t-fabs(dx-sx)-fabs(dy-sy)-kt;//剪枝情况，  
  
if(time<0||time%2==1) return ;//如果走到终点而时间有多余，但是多出时间为起点到终点时间的奇数倍，还是不符合条件  
if(flag\[sx+1\]\[sy\]==0)//位置标记为0，则表示可走，无障碍物，\*\*\*\*向前走\*\*\*\*  
\{  
flag\[sx+1\]\[sy\]=1;//表示当前的狗位置，并且标记为1表示不可以走  
dfs(sx+1,sy,kt+1);//用递归的思想再次调用dfs函数,看是否进行下一步  
flag\[sx+1\]\[sy\]=0;//如果狗离开这个位置，那么该位置又恢复成可走  
\}  
if(flag\[sx\]\[sy+1\]==0)//\*\*\*向左走\*\*\*  
\{  
flag\[sx\]\[sy+1\]=1;//同理  
dfs(sx,sy+1,kt+1);  
flag\[sx\]\[sy+1\]=0;  
\}  
if(flag\[sx-1\]\[sy\]==0)//\*\*\*向后走\*\*\*  
\{  
flag\[sx-1\]\[sy\]=1;//同理  
dfs(sx-1,sy,kt+1);  
flag\[sx-1\]\[sy\]=0;  
\}  
if(flag\[sx\]\[sy-1\]==0)//\*\*\*向右走\*\*\*  
\{  
flag\[sx\]\[sy-1\]=1;//同理  
dfs(sx,sy-1,kt+1);  
flag\[sx\]\[sy-1\]=0;  
\}  
return ;  
\}  
int main()  
\{  
while(cin>>n>>m>>t)  
\{  
getchar();  
if(n==0&&m==0&&t==0) break;  
memset(map,0,sizeof(map));  
memset(flag,1,sizeof(flag));  
wall=0;  
for(int i=1;i<=n;i++)  
\{  
for(int j=1;j<=m;j++)  
\{  
cin>>map\[i\]\[j\];//初始化二维数组，布置地图  
if(map\[i\]\[j\]=='S')//将S作为起点的位置  
\{  
flag\[i\]\[j\]=0;  
sx=i;  
sy=j;  
\}  
else if(map\[i\]\[j\]=='D')//将D作为终点的位置  
\{  
flag\[i\]\[j\]=0;  
dx=i;  
dy=j;  
\}  
else if(map\[i\]\[j\]=='X')//将X作为障碍物  
\{  
block++;  
\}  
else if(map\[i\]\[j\]=='.')//将.作为可走，所以标记为0  
\{  
flag\[i\]\[j\]=0;  
\}  
\}  
getchar();  
\}  
ans=0;  
flag\[sx\]\[sy\]=1;//初始化起点 并把起点标记为不可走  
if((n\*m-block)<=t)//如果所有的步数减去障碍物的数目，小于时间，则无法达到要求，这也是属于剪枝情况  
cout<<"NO"<<endl;  
else  
\{  
dfs(sx,sy,0);//从起点开始搜索，并把时间初始化为0；  
if(ans) cout<<"YES"<<endl;  
else cout<<"NO"<<endl;  
\}  
\}  
return 0;  
\}