Hdu1010Tempter of the Bone 深搜+剪枝
2024-08-26 20:12:46
题意:输入x,y,t.以及一个x行y列的地图,起点‘S’终点‘D’地板‘.’墙壁‘X’;判断能否从S正好走t步到D。
题解:dfs,奇偶性减枝,剩余步数剪枝。
ps:帮室友Debug的题:打错了两个字母。题目看错。没有初始化map。orz ...不过我dfs也不熟,更别说剪枝了。
//#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
int n, m, T;
int si, sj, ei, ej;
char a[][];
int map[][];
int dir[][] = { { , },{ -, },{ , },{ ,- } };
int check(int i, int j, int t) {
if (i< || i >= n || j< || j >= m || map[i][j] || a[i][j] == 'X') return false; return true;
}
bool dfs(int i, int j, int t) { if (i == ei&&j == ej&&t==T) return true;
if (t>=T) return false;
map[i][j] = ;
for (int k = ; k<; k++) {
int di = i + dir[k][];
int dj = j + dir[k][];
if (!check(di, dj, t + )) continue;
if (dfs(di, dj, t + ))
return true;
map[di][dj] = ;
}
return false;
}
int main() {
while (~scanf("%d%d%d", &n, &m, &T)) {
if (n == && m == && T == ) break;
memset(map, , sizeof(map));
for (int i = ; i<n; i++)
scanf("%s", a[i]);
int ok = ;
for (int i = ; i<n; i++) {
for (int j = ; j<m; j++) {
if (a[i][j] == 'D') {
ei = i; ej = j;
ok++;
}
if (a[i][j] == 'S') {
si = i; sj = j;
ok++;
}
if (ok == ) break;
}
if (ok == ) break;
}
if ((T - (abs(ei - si) + abs(ej - sj))) % || (T - (abs(ei - si) + abs(ej - sj)))<) printf("NO\n");
else if (dfs(si, sj,)) printf("YES\n");
else printf("NO\n");
}
return ;
}
最新文章
- Spark ML聚类分析之k-means||
- Check the difficulty of problems(POJ 2151)
- Linux Shell查看磁盘分区,内存使用,CPU使用率
- php ++a和a++
- Android (cocos2dx 网络访问)访问权限设置
- Cocos2d-JS地图性能问题
- D3D11_USAGE使用
- TCP/IP协议三次握手与四次握手流程解析(转载及总结)
- 使用Javascript 实现类
- PHP编程----猴子选大王
- 利用jQuery移除和添加图片
- 附录D——自动微分(Autodiff)
- ZOJ 2477 Magic&#160;Cube(魔方)
- 20165235 学习基础和C语言基础调查
- Android hdpi ldpi mdpi xhdpi xxhdpi适配详解
- xtrabackup备份mysql-2 增量备份
- R语言实战(四)—— 基本数据管理
- MenOS
- cmd下查看应用端口情况
- bootStrap中Tab页签切换