本文主要是介绍hdu---1010 Tempter of the Bone （经典DFS，注意剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*经典的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;
}
这篇关于hdu---1010 Tempter of the Bone （经典DFS，注意剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
