- 浏览: 37479 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23728 Accepted Submission(s): 6527
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output
NO YES
Author
ZHANG, Zheng
Source
Recommend
尼条题目我WA = 47次, TLE = 3次。
其实尼条题目既精粹就在于奇偶剪枝,同埋判断剩余可行格数。
剩余格数可以理解,但系咩系奇偶剪枝?baidu好多解答,呢度我吾讲啦{= =}。
呢个博文重点讲一D小技巧,同埋要注意既地方。
下面先贴代码:
4266151 | 2011-07-27 10:20:41 | Accepted | 1010 | 46MS | 288K | 1132 B | C++ | 10SGetEternal{(。)(。)}! |
#include <iostream> using namespace std; #define MAXI 11 #define ABS(x) ((x) > 0? (x): -(x)) char maz[MAXI][MAXI]; int n, m, t, sx, sy, ex, ey, blo; int mov[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; bool DFS(int x, int y, int st) { int dt = t - st - ABS(ex - x) - ABS(ey - y); int i, tx, ty; char tc = maz[x][y]; if (st == t && x == ex && y == ey) return 1; if (dt < 0 || dt % 2 == 1) return 0; maz[x][y] = 'X'; for (i = 0; i < 4; i++) { tx = x + mov[i][0]; ty = y + mov[i][1]; if (0 <= tx && tx < n && 0 <= ty && ty < m && maz[tx][ty] != 'X') if (DFS(tx, ty, st + 1)) return 1; } maz[x][y] = tc; return 0; } int main() { int i, j; while (cin >> n >> m >> t, n || m || t) { for (blo = i = 0; i < n; i++) { //getchar(); for (j = 0; j < m; j++) { cin >> maz[i][j]; //scanf("%c", maz[i] + j); if (maz[i][j] == '.') blo++; if (maz[i][j] == 'S') { sx = i; sy = j; } if (maz[i][j] == 'D') { ex = i; ey = j; blo++; } } } if (blo >= t && DFS(sx, sy, 0)) printf("YES\n"); else printf("NO\n"); } return 0; }
首先重点讲一下WA杀手getchar()
我之前一直无留意呢个地方…………用getchar配合scanf其实要系测试数据无多余空行前提下可以用,杭电测试数据……
所以我就WA好多次都唔知死系边度……改cin之后就AC鸟。
TLE有两次系因为我用maz[x][y] == 'D'判断搜索结束,其实甘样系有问题,因为我地通常改标记会原地改,搜索完一轮之后就原地复原,
不过因为尼条题目特性系要t == tim同时到达D先符合条件,所以有可能某次搜索到达左D但系t > tim,而且呢轮搜索完结之后,又唔记得
复原'D'而系直接赋'.',所以之后就搵唔到D啦。解决呢个问题有两个方法:一、用坐标判断。二、用一个变量储存标记前坐标。
就系甘样浪费左一日
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1189Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 865What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1218Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 814find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 1012Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 762box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 844Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 1025Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1207二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 1024Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 901Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 794Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1061分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1279Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1119Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 679Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 601find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 702N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 793Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 671开门人和关门人 Time Limit: 2000/1000 ...
相关推荐
例如,"HDU1010 Tempter of the Bone.cpp"可能就是利用DFS解决了一种寻找最短路径或解谜的问题。 另一方面,广度优先搜索(BFS)则是一种从根节点开始,逐层搜索直至找到目标的算法。BFS通常用于找出图中两个节点的...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...
这个压缩包文件包含的是从HDU题目ID1010到2500之间的部分解题报告,对于想要提升编程能力、学习算法知识的ACMer来说,是一份宝贵的资源。 这些解题报告通常会包含以下几个方面的重要知识点: 1. **题目描述**:每...
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
解题报告|ACM|程序设计参考程序以及题目的分析
HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...
【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...
本报告围绕“ACM.rar”这个压缩包,我们将深入探讨其中涉及到的三道题目——HDU1010、ZOJ1010和ZOJ1015,并分享一些原创解题思路,尽管这些算法可能并非最优,但它们为我们提供了一种独特的视角来理解和解决问题。...
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...
* 题目1010:Tempter of the Bone,涉及到递归搜索的概念。 * 题目1016:Prime Ring Problem,涉及到递归搜索的概念。 * 题目1026:Ignatius and the Princess I,涉及到完全搜索的概念。 2. 图的遍历:深度优先...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...
搜索题是 ACM HDU 题目分类中的一大类,例如,1010 搜索题,剪枝很关键;1016 经典的搜索;1026 搜索;1043 经典搜索题,八数码问题;1044 稍微有点麻烦的搜索题;1045 搜索题,可用匹配做 等等。 贪心算法 贪心...