#include<cstdio>
#include<cmath>
#include<stdlib.h>
int dir[][]={{,},{,-},{,},{-,}},escape,n,m,t,si,sj,ei,ej;
char a[][];
void dfs(int si,int sj,int cnt)
{
if(si<||si>=n||sj<||sj>=m)
return ;
if(si==ei&&sj==ej&&cnt==t)
{
escape=;
return;
}
int temp=t-cnt-abs(ei-si)-abs(ej-sj);
if(temp<||temp%)
return ;
for(int i=;i<;i++)
{
if(a[si+dir[i][]][sj+dir[i][]]!='X')
{
a[si+dir[i][]][sj+dir[i][]]='X';
dfs(si+dir[i][],sj+dir[i][],cnt+);
if(escape)
return;
a[si+dir[i][]][sj+dir[i][]]='.';
}
}
return; }
int main()
{
int wall=;
while(scanf("%d%d%d",&n,&m,&t))
{
wall=;
escape=;
if(n==&&m==&&t==) break;
getchar();
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
scanf("%c",&a[i][j]);
if(a[i][j]=='S')
{
si=i;
sj=j;
}
if(a[i][j]=='X')
wall++;
if(a[i][j]=='D')
{
ei=i;
ej=j;
}
}
getchar();
}
if(n*m-wall<=t)
{
printf("NO\n");
continue;
}
a[si][sj]='X';
dfs(si,sj,);
if(escape)
printf("YES\n");
else
printf("NO\n");
}
return ;
}

正式开始学习和练习DFS、BFS,先从这DFS道中最入门的题开始。

关键:剪枝。

最新文章

  1. python第一站
  2. windows update一直卡住:“正在此计算机上搜索更新”
  3. SPSS数据分析—配对Logistic回归模型
  4. 51单片机对无线模块nRF24L01简单的控制收发程序
  5. android:ToolBar详解(手把手教程)(转)
  6. nginx TCP 代理&amp; windows傻瓜式安装
  7. Android 自定义NumProgressBar
  8. 安装tar.bz2文件
  9. mfc学生成绩录入与查询
  10. C++ Stacks(堆栈)
  11. oracle权限的分配
  12. bzoj 2209 [Jsoi2011]括号序列 平衡树
  13. Zookeeper的安装部署
  14. springmvc中只接受固定提交内容类型的请求
  15. python3三角函数
  16. 洛谷P4774 [NOI2018]屠龙勇士 [扩欧,中国剩余定理]
  17. 【转载】C++ ,C#数据类型对照
  18. Laravel 的十八个最佳实践
  19. python 之面向对象
  20. Sencha Touch 扩展集合

热门文章

  1. iOS开发之.pch文件初识
  2. Linux配置全局环境变量的方法
  3. hadoop 入门实例【转】
  4. 转:一个Sqrt函数引发的血案
  5. 使用Python获取Linux系统的各种信息
  6. PHP 实现多服务器共享 SESSION 数据
  7. Hbase之获取数据
  8. Windows CPU占用率过高
  9. JavaScript 运行机制详解:再谈Event Loop
  10. ubuntu下python3安装类库