题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目前提条件:让你输入一个数组,包含一个起点S,一个终点D,一个时间T。(其中X代表墙,.代表此地可行。)

题目要求:在规定的第T秒,问你是否能够走出迷宫。(每走一步耗时1s)。

解题方法:DFS+vis[][]+flag+(新技巧)奇偶剪枝。

#include<iostream>
#include<string.h>
#include<cmath>;
using namespace std; char map[][];
int vis[][]; //(新增)访问标记的数组
int N,M,T;
int sx,dx,sy,dy;
int flag; //(新增)判断状态
int k; //(新增)记录障碍物的个数 int abs(int a,int b)
{
if(a<b)
{
return b-a;
}
else
{
return a-b;
}
} void dfs(int x,int y,int dep) //void()函数内使用“return;”表示跳出此函数。
{
if(dep>T)
{
return ;
}
if(x<||x>=N||y<||y>=M)
{
return ;
} if(flag)
{
return;
}
if(map[x][y]=='D'&&dep==T)
{
flag=;
return ;
} int temp=abs(x-dx)+abs(y-dy); //(新增)奇偶剪枝
temp=T-temp-dep;
if(temp&) //if(走不下去了)
{
return;
} //枚举下一种情况,DFS(...,dep+1);
if(!vis[x-][y]&&map[x-][y]!='X') //(新增)if(下一个点满足的情况)
{
vis[x-][y]=;
dfs(x-,y,dep+);
vis[x-][y]=;
}
if(!vis[x+][y]&&map[x+][y]!='X') //(新增)if(下一个点满足的情况)
{
vis[x+][y]=;
dfs(x+,y,dep+);
vis[x+][y]=;
}
if(!vis[x][y-]&&map[x][y-]!='X') //(新增)if(下一个点满足的情况)
{
vis[x][y-]=;
dfs(x,y-,dep+);
vis[x][y-]=;
}
if(!vis[x][y+]&&map[x][y+]!='X') //(新增)if(下一个点满足的情况)
{
vis[x][y+]=;
dfs(x,y+,dep+);
vis[x][y+]=;
} } int main()
{
while(cin>>N>>M>>T)
{
if(N==&&M==&&T==)
{
break;
} k=;
memset(vis,,sizeof(vis)); //(新增)访问标记数组的初始化。 for(int i=;i<N;i++)
{
for(int j=;j<M;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
sx=i;
sy=j;
vis[i][j]=; //(新增)给起点作“已访”标记
}
if(map[i][j]=='D')
{
dx=i;
dy=j;
} if(map[i][j]=='X')
{
k++; //(新增)记录障碍物的个数
}
}
} flag=; //(新增)初始状态为false; if(N*M-k->=T) //(新增)T+k+1(起点S的位置)必须 <= N*M(总的格子数)
{
dfs(sx,sy,);
} if(flag)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
} }
}

最新文章

  1. web 打开子窗口提交数据或其他操作后 关闭子窗口且刷新父窗口实现
  2. 通过innobackupex实现对MySQL的完整备份与还原
  3. RelativeLayout用到的一些重要的属性:
  4. oracle 时间函数
  5. JQuery里的原型prototype分析
  6. 利用Qt调用计算器
  7. Unity Fresnel Hero(Dota2) Shader
  8. hbase学习笔记-----REST客户端
  9. 设置dialog显示,自定义时间到后dialog消失
  10. Android基础之CountDownTimer 倒计时类
  11. 更改DataTable列名方法
  12. truncate 和 delete 差异
  13. Android开发之漫漫长途 Ⅳ——Activity的显示之ViewRootImpl初探
  14. TCP/IP,Web世界的基本规则
  15. hdu 1394 逆序对(nlgn+o(n) )
  16. 9、Qt Project之简单的数据库接口
  17. day07 深浅拷贝
  18. redis排序
  19. 记一次线上bug排查-quartz线程调度相关
  20. Java SE学习【三】——JDBC

热门文章

  1. 【Linux常见命令】pwd命令
  2. BlackNurse攻击:4Mbps搞瘫路由器和防火墙
  3. 11.25-11.27 配置防盗链,访问控制(Directory,FilesMatch)
  4. linux系统单网卡绑定多个IP地址
  5. echarts自定义tooltip显示
  6. 解决iframe跨域刷新的问题
  7. awk调用date命令
  8. OpenCV 经纬法将鱼眼图像展开
  9. mongodb windows 集群搭建
  10. css布局的漂浮、position定位