(DFS)hdoj1010-Tempter of the Bone
2024-08-24 02:43:52
#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道中最入门的题开始。
关键:剪枝。
最新文章
- python第一站
- windows update一直卡住:“正在此计算机上搜索更新”
- SPSS数据分析—配对Logistic回归模型
- 51单片机对无线模块nRF24L01简单的控制收发程序
- android:ToolBar详解(手把手教程)(转)
- nginx TCP 代理&; windows傻瓜式安装
- Android 自定义NumProgressBar
- 安装tar.bz2文件
- mfc学生成绩录入与查询
- C++ Stacks(堆栈)
- oracle权限的分配
- bzoj 2209 [Jsoi2011]括号序列 平衡树
- Zookeeper的安装部署
- springmvc中只接受固定提交内容类型的请求
- python3三角函数
- 洛谷P4774 [NOI2018]屠龙勇士 [扩欧,中国剩余定理]
- 【转载】C++ ,C#数据类型对照
- Laravel 的十八个最佳实践
- python 之面向对象
- Sencha Touch 扩展集合