hdu1010 - dfs,奇偶剪枝
2024-08-31 12:49:43
给一个迷宫,问从起点到终点存不存在一条长度为T的路径。
-----------------------------------------------------------------------------
判断(T-当前步数)的奇偶性 和 (终点-当前位置)距离的奇偶性是否相同。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
typedef long long LL;
using namespace std;
const int N = ;
const int skip[][] = { { , }, { -, }, { , }, { , - } }; int m, n, t;
int sx, sy, ex, ey;
char maze[N][N];
bool vis[N][N];
bool judge(int x, int y){
if (x< || y< || x >= m || y >= n) return false;
if (vis[x][y]) return false;
if (maze[x][y] == 'X') return false;
return true;
} bool dfs(int x, int y, int step){
if (x == ex&&y == ey&&step == t) return true;
int tag = t - step - abs(ex-x) - abs(ey-y);
if(tag<||tag&) return false;
for (int i = ; i<; i++){
int tx = x + skip[i][];
int ty = y + skip[i][];
if (judge(tx, ty)){
vis[tx][ty] = true;
if (dfs(tx, ty, step + )) return true;
vis[tx][ty] = false;
}
}
return false;
} int main(){
while (scanf("%d%d%d", &m, &n, &t), m + n + t){
for (int i = ; i<m; i++) {
scanf("%s", maze[i]);
for (int j = ; j<n; j++){
if (maze[i][j] == 'D') sx = i, sy = j;
if (maze[i][j] == 'S') ex = i, ey = j;
}
}
memset(vis, false, sizeof(vis)); if (dfs(sx,sy,)) puts("YES");
else puts("NO");
}
return ;
}
最新文章
- 极光推送-适配 iOS10
- [置顶] 关于产品的一些思考——腾讯之UIDesigner
- 应用highcharts做直观数据统计
- RabbmitMQ集群搭建流程
- java javaScript实现遮罩层 动态加载
- messagebox在最顶层写法
- Bitmap 格式
- Java报错信息 java.lang.SecurityException: Prohibited package name: java.xxx
- 微信网页授权获取用户openid及用户信息
- 【java工具】java常用工具
- entity framework异常 The specified cast from a materialized &#39;System.Int32&#39; type to the &#39;System.String&#39; type is not valid
- jquery实现右键菜单
- CentOS SVN服务器管理多项目
- centos 打包报错License for package Android SDK Build-Tools 25.0.3 not accepted
- 微信h5支付“网站域名ICP备案主体与商户号主体不一致”的解决方法,H5微信支付 授权函下载
- 检测QQ在线状态脚本(20141022测试成功)
- [BZOJ4557][JLOI2016]侦察守卫(树形DP)
- Sublime key
- kaggle kernel使用指南
- 利用json2html将json数据填充到html模板