HDU 1010 Tempter of the Bone (DFS+剪枝)
The of HDU DFS 剪枝
2023-09-11 14:17:18 时间
题意:从S走到D,能不能恰好用T时间。
析:这个题时间是恰好,并不是少于T,所以用DFS来做,然后要剪枝,不然会TEL,我们这样剪枝,假设我们在(x,y),终点是(ex,ey),
那么从(x, y)到(ex, ey),要么时间正好是T-你已经走过的时间,要么要向别的地方先拐一下,以凑出这个正好时间,既然要拐一下,那么一定要回来,
所以时间肯定得是偶数,要不然完不成(回不来),
所以(t - abs(ex-x) - abs(ey-y) - cnt ),如果是奇数就剪枝。然而用C++交就TLE,用G++就AC。。。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> using namespace std ; typedef long long LL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const double inf = 0x3f3f3f3f3f3f3f; const double eps = 1e-8; const int maxn = 1e4 + 5; const int mod = 1e9 + 7; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; int n, m; inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m; } int t; char s[10][10]; int vis[10][10]; int sx, sy, ex, ey; bool dfs(int r, int c, int cnt){ if(cnt > t) return false; if(r == ex && c == ey && cnt == t) return true; if((t - abs(ex-r) - abs(ey-c) - cnt) & 1) return false; for(int i = 0; i < 4; ++i){ int x = dr[i] + r; int y = dc[i] + c; if(!is_in(x, y) || vis[x][y] || s[x][y] == 'X') continue; vis[x][y] = 1; if(x == ex && ey == y && cnt + 1 == t) return true; if((t - abs(ex-x) - abs(ey-y) - cnt -1) & 1) continue; if(dfs(x, y, cnt+1)) return true; vis[x][y] = 0; } return false; } int main(){ while(scanf("%d %d %d", &n, &m, & t) == 3){ if(!n && !m && !t) break; for(int i = 0; i < n; ++i) scanf("%s", s[i]); for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(s[i][j] == 'S') sx = i, sy = j; else if(s[i][j] == 'D') ex = i, ey = j; memset(vis, 0, sizeof(vis)); vis[sx][sy] = 1; if(dfs(sx, sy, 0)) puts("YES"); else puts("NO"); } return 0; }
相关文章
- maven 下载jar失败: resolution will not be reattempted until the update interval of central has elapsed or updates are forced
- ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(二)
- 【异常】The dependencies of some of the beans in the application context form a cycle
- Bower : ENOGIT git is not installed or not in the PATH
- SQL SERVER 2005删除维护作业报错:The DELETE statement conflicted with the REFERENCE constraint "FK_subplan_job_id"
- [Angular] Control the dependency lookup with @Host, @Self, @SkipSelf and @Optional
- (纪录片)《星际穿越》中的科学 The Science of Interstellar
- [React] Directly Dispatch Actions into the Redux Store Before React Renders
- [React] Use the Fragment Short Syntax in Create React App 2.0
- [Python] Create a minimal website in Python using the Flask Microframework
- [Python] Finding the most common elements in an iterable
- The CPU Costing Model: A Few Thoughts Part IV (Map of the Problematique)
- How to handle the generic error Cannot read property md of undefined
- 【23.48%】【codeforces 723C】Polycarp at the Radio
- The resource could not be loaded because the App Transport Security policy requires the use of a sec
- NLP:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的参考文献
- 成功解决The following specifications were found to be incompatible with the existing python installation
- 成功解决ERROR: Could not find a version that satisfies the requirement xgboost (from versions: none) ERR
- 成功解决KeyError: “Passing list-likes to .loc or [] with any missing labels is no longer supported. The
- 成功解决VirtualBox is not installed. Please re-run the Toolbox Installer and try again.
- 已解决The above exception was the direct cause of the following exception:
- 已解决TypeError: the JSON object must be str, bytes or bytearray, not dict
- 关于appium踩坑 :Encountered internal error running command: Error: Cannot verify the signature of (已解决)
- 魔戒 (The Lord of the Rings,又译《指环王》)
- 论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
- HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树
- 数学原理(The Principles of Mathmatics)
- 【异常】Flyway failed to initialize: none of the following migration scripts locations could be found