Tempter of the Bone------剪枝
2024-08-31 16:52:09
看了好多别人的 代码,最终还是 感觉 这种代码的风格适合我 下面附上代码
/* 首先 应该充满信心! 先写出来 自己的程序 然后慢慢改 ,
如果是 答题思路错误的话 借鉴别人的 代码 再写
*/
/*没有剪枝 时间超限*/
#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 ;
}
最新文章
- BootStrap学习笔记,优缺点总结
- Jackson fasterxml跟codehaus的区别 (fasterxml vs. codehaus) -- 转载
- c# Sqlite帮助类
- Mac下搭建go语言开发环境
- MySQL 5.6 复制:GTID 的优点和限制(第一部分)
- 从一道面试题谈linux下fork的运行机制
- 基于visual Studio2013解决C语言竞赛题之1034数组赋值
- Maven之(一)Maven是什么
- LeetCode OJ 217.Contains Duplicate
- 详解spl_autoload_register()函数
- 转载:selenium webdriver定位不到元素的五种原因及解决办法
- 接口自动化:HttpClient + TestNG + Java(一) - 接口测试概述+自动化环境搭建
- day06(深浅拷贝,元组,字典,集合)
- redis的 rdb 和 aof 持久化的区别
- CodeBlocks中我遇到的无法调试问题及解决方案
- Codeforces Round #491 (Div. 2)
- NumPy 学习笔记(二)
- MS-DOS 系统汇编环境之DOSBOX+vim
- CF 489C 暴力处理
- MySQL 组合查询 concat