`

HDU 1010 Tempter of the Bone .

阅读更多

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.
 

 

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.
 

 

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啦。解决呢个问题有两个方法:一、用坐标判断。二、用一个变量储存标记前坐标。
 
就系甘样浪费左一日发火
分享到:
评论

相关推荐

    ACM.zip_visual c

    例如,"HDU1010 Tempter of the Bone.cpp"可能就是利用DFS解决了一种寻找最短路径或解谜的问题。 另一方面,广度优先搜索(BFS)则是一种从根节点开始,逐层搜索直至找到目标的算法。BFS通常用于找出图中两个节点的...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu5102.zip_K.

    标题中的"hdu5102.zip_K."暗示这是一个与编程竞赛相关的题目,通常在HDU(杭州电子科技大学)在线判题系统中出现。这个题目可能是一个编程挑战,要求参赛者解决一个特定的问题,并提交源代码以供自动评判。"K."可能...

    HDU 1010-2500解题报告

    这个压缩包文件包含的是从HDU题目ID1010到2500之间的部分解题报告,对于想要提升编程能力、学习算法知识的ACMer来说,是一份宝贵的资源。 这些解题报告通常会包含以下几个方面的重要知识点: 1. **题目描述**:每...

    hdu1010搜索算法

    杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    HDU 2000-2099 解题报告.CHM

    解题报告|ACM|程序设计参考程序以及题目的分析

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    HDU-GO v19.1225.2.zip

    【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...

    ACM.rar_ACM 绠楁硶_HDU1010_hdu 18

    本报告围绕“ACM.rar”这个压缩包,我们将深入探讨其中涉及到的三道题目——HDU1010、ZOJ1010和ZOJ1015,并分享一些原创解题思路,尽管这些算法可能并非最优,但它们为我们提供了一种独特的视角来理解和解决问题。...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    HDU图论题目分类

    * 题目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.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU1019(2028)解题报告

    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

    【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...

    ACM HDU题目分类

    搜索题是 ACM HDU 题目分类中的一大类,例如,1010 搜索题,剪枝很关键;1016 经典的搜索;1026 搜索;1043 经典搜索题,八数码问题;1044 稍微有点麻烦的搜索题;1045 搜索题,可用匹配做 等等。 贪心算法 贪心...

Global site tag (gtag.js) - Google Analytics