学习剪枝的第一篇@_@
学习别人的剪枝,一剪就是两天@_@----

参看的这篇--
http://blog.csdn.net/libin56842/article/details/8962512
自己的小体会--
奇偶剪枝可以举两个一般的例子
比如样例
S.X.
..X.
..XD
....
转化为所需要的步数
S 6 X 2
6 5 X 1
5 4 X D
4 3 2 1
可以看到步数为奇数的时候,所需要的时间也为奇数
步数为偶数的时候,需要的时间也为偶数(因为是一秒走一步)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
int n,m,t,flag,di,dj,wall;
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
char map[10][10]; void dfs(int si,int sj,int cnt)
{
int tem;
if(si<=0||sj<=0||si>n||sj>m)
return;
if(si==di&&sj==dj&&cnt==t) flag=1;
if(flag) return; tem=t-cnt-abs(di-si)-abs(dj-sj);
if(tem<0||tem%2)
return; for(int i=0;i<4;i++)
{
if(map[si+dir[i][0]][sj+dir[i][1]]!='X')
{
map[si+dir[i][0]][sj+dir[i][1]]='X';
dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
map[si+dir[i][0]][sj+dir[i][1]]='.';
}
}
return;
}
int main()
{
int si,sj;
while(scanf("%d %d %d",&n,&m,&t)!=EOF&&n&&m&&t)
{
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') {si=i;sj=j;}
else if(map[i][j]=='D') { di=i;dj=j;}
else if(map[i][j]=='X')
wall++;
}
} if(n*m-wall<=t)
{
printf("NO\n");
continue;
}
flag=0;
map[si][sj]='X';
dfs(si,sj,0);
if(flag)
printf("YES\n");
else
printf("NO\n");
}
}

  

最新文章

  1. TypeScript
  2. jee websocket搭建总结
  3. PHP require class
  4. 整理的mysql优化内容
  5. uva 11020 - Efficient Solutions ——平衡BST
  6. ubuntu安装后没有root密码
  7. php校验
  8. 让你的 Node.js 应用跑得更快的 10 个技巧
  9. MySQL PrepareStatement基本的两种模式&amp;客户端空间占用的源码分析
  10. 求N!末尾的0的个数(找规律+递归)
  11. 多人开发的git项目如何保持提交日志为一条直线?
  12. 某集团BI决策系统建设方案分享
  13. 怎么动态生成js变量
  14. Cygwin工具安装和使用指导书
  15. JS变量声明方式
  16. 进入正在运行的 docker 容器(docker container)
  17. 生成和打上patch的方法(转载)
  18. windows库的创建和使用:静态库+动态库
  19. 3D空间中射线与三角形的交叉检测算法【转】
  20. 遇到执行SQL 的参数最大个数

热门文章

  1. Team Services 自动化部署项目
  2. mybatis通用的crud的接口
  3. 一个基于Angular+Ionic+Phonegap的混合APP实战
  4. React router内是如何做到监听history改变的
  5. iOS11访问相册权限变更问题
  6. addFooterView(v)与 addHeaderView(v)之后 头或者尾部没有加上去
  7. Android ImageView 替换图片
  8. 前端精选文摘:css之BFC 神奇背后的原理(转载)
  9. Eclipse安装不了AXIS2 Tool插件,总是找不到axis2 wizards的问题找到解决答案(转载)
  10. Django中模块的加载原理