看了好多别人的  代码,最终还是 感觉 这种代码的风格适合我  下面附上代码

 /* 首先 应该充满信心!  先写出来 自己的程序  然后慢慢改 ,
如果是 答题思路错误的话 借鉴别人的 代码 再写
*/
/*没有剪枝 时间超限*/
#include<stdio.h>
#include<string.h>
char a[][];
int visited[][];
int s[][]={-,,,,,-,,};
int n,m,t,bx,by,cx,cy,step=,mark;
void DFS(int y,int x,int step) // 传输 进去现在 的 位置 并且传出过去 已有的 步数
{
if(y==cy&&x==cx&&step==t)
{
mark=;
}
visited[y][x]=;
for(int i=;i<;i++)
{
if(a[y+s[i][]][x+s[i][]]!='X'&&(y+s[i][])>=&&(y+s[i][])<n&&(x+s[i][])>=&&(x+s[i][])<m&&!visited[y+s[i][]][x+s[i][]]) // 不超界 并且 不是墙 而且没有访问
{
step++;
DFS(y+s[i][],x+s[i][],step);
step--;
} }
visited[y][x]=;
}
int main()
{
int i,j;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
if(n==&&m==&&t==)
break
getchar();
memset(visited,,sizeof(visited));
for(mark=step=i=;i<n;i++)
{
for(j=;j<m;j++)
{
scanf("%c",&a[i][j]);
if(a[i][j]=='S') // 找到进入的坐标
{
bx=j;
by=i;
}
if(a[i][j]=='D') // 找到出去的坐标
{
cx=j;
cy=i;
}
}
getchar();
}
DFS(by,bx,); // 传输 当前座标
if(mark!=)
printf("NO\n");
else
printf("YES\n");
}
return ;
}

上面的 没有剪枝  时间超限   下面开始 剪枝  .

 /* 首先 应该充满信心!  先写出来 自己的程序  然后慢慢改 , 如果是 答题思路错误的话 借鉴别人的 代码 再写  */
/*
剪枝:
1: 奇偶剪枝:到终点的最短步数(就算需要绕路也没事要的奇偶) 和 到终点限定的步数 如果 奇偶性不同的话是不可能达到的 (绕路是同时多出偶数倍的步数) 1/2 的时间
2: 进去的时候 到 终点的最短路 如果大于 给定的步数 也不可能 . (也可能绕路绕超所以需要重复)
3: 可以走的格子 走完但是仍然还不够限定的步数 就不行了
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<cctype>
#include<limits.h>
#define leng 10
using namespace std;
char a[leng][leng];
int ex,ey,n,m,t,bx,mark,by,b[][]={,,,,,-,-,},visited[leng][leng];
void DFS(int y,int x,int step)
{
int d=t-step-abs(y-ey)-abs(x-ex); // 剩下 的步数 - 到终点的步数 小于 0 完蛋 .
if(t<step||mark==||d<||d%) // 这里三个 剪枝 . 上述公式 如果不是 偶数的话 , 就完蛋.
return;
if(a[y][x]=='D'&&t==step)
{
mark=;
}
visited[y][x]=;
for(int i=;i<;i++)
{
int tx=x+b[i][],ty=y+b[i][];
if(a[ty][tx]!='X'&&tx>=&&tx<m&&ty>=&&ty<n&&!visited[ty][tx]) // 不是 墙 不超界 没用过
{
DFS(ty,tx,step+);
}
}
visited[y][x]=;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t),!(n==m&&m==t&&t==))
{
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='S')
{
bx=j;
by=i;
}
if(a[i][j]=='D')
{
ex=j;
ey=i;
}
}
}
memset(visited,,sizeof(visited));
mark=;
DFS(by,bx,);
if(mark==)
printf("NO\n");
else
printf("YES\n");
}
return ;
}

最新文章

  1. BootStrap学习笔记,优缺点总结
  2. Jackson fasterxml跟codehaus的区别 (fasterxml vs. codehaus) -- 转载
  3. c# Sqlite帮助类
  4. Mac下搭建go语言开发环境
  5. MySQL 5.6 复制:GTID 的优点和限制(第一部分)
  6. 从一道面试题谈linux下fork的运行机制
  7. 基于visual Studio2013解决C语言竞赛题之1034数组赋值
  8. Maven之(一)Maven是什么
  9. LeetCode OJ 217.Contains Duplicate
  10. 详解spl_autoload_register()函数
  11. 转载:selenium webdriver定位不到元素的五种原因及解决办法
  12. 接口自动化:HttpClient + TestNG + Java(一) - 接口测试概述+自动化环境搭建
  13. day06(深浅拷贝,元组,字典,集合)
  14. redis的 rdb 和 aof 持久化的区别
  15. CodeBlocks中我遇到的无法调试问题及解决方案
  16. Codeforces Round #491 (Div. 2)
  17. NumPy 学习笔记(二)
  18. MS-DOS 系统汇编环境之DOSBOX+vim
  19. CF 489C 暴力处理
  20. MySQL 组合查询 concat

热门文章

  1. vim基础(二)
  2. mesh topology for airfoil, wing, blade, turbo
  3. average column data from multiple files
  4. 洛谷P1028数的计算
  5. 类中的普通方法伪装成属性 @property
  6. Android第三方开源SwitchButton
  7. [luoguP2760] 科技庄园(背包DP)
  8. 【BZOJ1014】火星人prefix(splay,Hash)
  9. 洛谷—— P1419 寻找段落
  10. T1462 素数和 codevs