`

hdu 1010 Tempter of the Bone

    博客分类:
  • dfs
阅读更多

Tempter of the Bone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24023    Accepted Submission(s): 6616

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
 

      这题与普通的走迷宫有些不相同之处:1.规定那个时间到达(不是规定时间内到达);2.走过的路不能再走。第一次做超时了,要剪枝,后来想到有一个重要剪枝---奇偶剪枝!写了就AC了。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010

代码:

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

bool step[8][8];
char ch[15][15];
int n, m, s, flag;

void init()
{
    flag = 0;
    memset(step, false, sizeof(step));
}

void dfs(int x, int y, int t)
{
    if(flag) return;                    //若已经找到,返回
    if(x<0 || y<0 || x>=n || y>=m) return;  //若越界,返回
    if(t > s) return;       //若时间已经超过出现时间,返回
    if(ch[x][y] == 'X') return;             //若是墙,返回
    if(ch[x][y] == 'D')
    {
        if(t==s)    //若时间刚刚好
        {
            flag = 1;
            return;
        }
        //重要剪枝:去到'D'点是偶数(奇数)步,那它出来的时间一定要偶数(奇数)才能去到
        if(t%2 != s%2)
        {
            flag = 2;
            return;
        }
    }
    if(step[x][y]) return;  //若该点已经走过,则返回
    step[x][y] = true;      //否则,更新该点为走过,并开始搜索

    //往4个方向进行dfs深搜
    dfs(x+1, y, t+1);
    dfs(x-1, y, t+1);
    dfs(x, y+1, t+1);
    dfs(x, y-1, t+1);

    step[x][y] = false;     //若该点是走不通的,更新该点为未走过,往上一步退

}

int main()
{
    int i, j;
    while(scanf("%d %d %d", &n, &m, &s) != EOF)
    {
        if(!m && !n && !s) break;
        init();
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                cin>>ch[i][j];
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                if(ch[i][j] == 'S')
                    dfs(i, j, 0);   //找到入口,开始搜索

        if(flag == 1) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

 

3
16
分享到:
评论

相关推荐

    HDU图论题目分类

    * 题目1010:Tempter of the Bone,涉及到递归搜索的概念。 * 题目1016:Prime Ring Problem,涉及到递归搜索的概念。 * 题目1026:Ignatius and the Princess I,涉及到完全搜索的概念。 2. 图的遍历:深度优先...

    ACM.zip_visual c

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

    HDU 1010-2500解题报告

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

    hdu1010搜索算法

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

    ACM.rar_ACM 绠楁硶_HDU1010_hdu 18

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

    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.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    ACM HDU题目分类

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

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    code_hdu.rar_ACM_The First_hdu_test case example

    The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). Output For each test case, print ...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

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

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

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

Global site tag (gtag.js) - Google Analytics