`
Simone_chou
  • 浏览: 182809 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Tempter of the Bone(DFS + 奇偶剪枝)

    博客分类:
  • HDOJ
 
阅读更多

 

Tempter of the Bone

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


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

    题意:

    给出N,M,T(N和M范围1到7,T为50)。代表有一个地图大小有N行M列,S为起点,D为终点,问是否能在T步从S走到D。(必须为T步,不能少于也不能大于)。

 

    思路:

    DFS。但是单纯的DFS会超时,所以要进行剪枝。奇偶剪枝。

 

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int endx,endy,t,temp,n,m,ans;
char map[10][10];
int vis[10][10],dir[4][2]={-1,0,0,-1,1,0,0,1};

void dfs(int x,int y)
{
    vis[x][y]=1;
 //   printf("x=%d y=%d\n",x,y);
    if(ans>t||temp) return;
//如果统计步数已经大于所要求步数,或者已经找到就不继续搜索了
    if(ans==t&&x==endx&&y==endy)
    {
        temp=1;
        return;
    }
//    if((abs(endx-x)+abs(endy-y))%2!=((t-ans)%2)) return;
    for(int i=0;i<4;i++)
    {
        int nx,ny;
        nx=x+dir[i][0];
        ny=y+dir[i][1];
        if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny]&&map[nx][ny]!='X')
        {
            ans++;
            dfs(nx,ny);
            vis[nx][ny]=0;
            ans--;
        }
    }
}

int main()
{
 //   freopen("text.in","r",stdin);
    int w;
    while(scanf("%d%d%d",&n,&m,&t)!=EOF&&(n+m+t))
    {
        int stax,stay;
        temp=0,ans=0,w=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='S') stax=i,stay=j;
            if(map[i][j]=='D') endx=i,endy=j;
            if(map[i][j]=='X') w++;
            }
//一开始判断一次就够了
        if((abs(endx-stax)+abs(endy-stay))%2!=(t%2))
        {
            printf("NO\n");
            continue;
        }
//奇偶剪枝
        if(n*m<w+t)
        {
            printf("NO\n");
            continue;
        }
        dfs(stax,stay);
        if(temp) printf("YES\n");
        else     printf("NO\n");
    }
    return 0;
}

 

分享到:
评论

相关推荐

    Tempter of the Bone 代码

    Tempter of the Bone 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0

    HDOJ_1010 Tempter of the Bone

    该题求解在给定的时间及条件下,判断是否存在一条从入口到出口的路。

    AD5933中文参考手册_AD5933_AD5933中文参考手册_AD5933中文手册_

    AD5933中文参考手册 ,AD5933是一款高精度的阻抗转换器系统解决方案

    quartus ii安装教程.docx

    quartus ii安装教程

    tensorflow_probability-0.3.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_privacy-0.5.1-py3-none-any.whl

    算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_recommenders-0.7.3-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    asp代码ASP基于WEB实验室设备管理系统设计(源代码+论文)

    asp代码ASP基于WEB实验室设备管理系统设计(源代码+论文)本资源系百度网盘分享地址

    JAVA毕业设计之springboot057洗衣店订单管理系统(springboot+mysql)完整源码.zip

    这个资源是一个基于Spring Boot和MySQL的洗衣店订单管理系统的完整源码。它包括了所有的源代码文件,以及一个详细的文档,可以帮助你理解和运行这个系统。这个系统的主要功能包括:用户注册和登录,下单,查看订单,修改订单,删除订单等。用户可以在系统中选择洗衣服务,然后提交订单。系统会自动计算订单的总价,并将其显示在用户的订单列表中。用户还可以查看自己的历史订单,以及每个订单的详细信息。此外,系统还包括了一个管理员模块。管理员可以查看所有的订单,以及对订单进行管理。他们可以修改订单的状态,例如将订单标记为已完成,或者取消订单。这个系统使用了Spring Boot框架,这是一个非常流行的Java开发框架,它可以帮助你快速地开发和部署应用程序。同时,系统也使用了MySQL数据库,这是一个广泛使用的关系型数据库,它可以存储大量的数据,并提供高效的查询功能。总的来说,这个资源是一个非常完整的洗衣店订单管理系统的源码,它可以帮助你理解如何使用Spring Boot和MySQL来开发一个实际的应用程序。无论你是正在学习Java编程,还是已经有一定的开发经验,都可以从这个资源中学到很多有用的知识和技能。

    网络药理学、代谢组学的应用

    网络药理学、代谢组学的应用和课题设计方案”基于PI3K-AKT-mTOR通路研究 淫羊藿苷影响成骨细胞糖酵解促进骨形成的机制“

    毕业论文知识图谱构建平台的python后端。模型相关在这个模块完成,深度学习基于pytorch.zip

    人工智能毕业设计&课程设计

    tensorflow_transform-0.1.4-py2-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    ftqqzx.zip

    ftqqzx.zip

    高级网络人才培训专家-X00070004 第31章 配置帧中继

    高级网络人才培训专家_X00070004 第31章 配置帧中继

    tensorflow_transform-0.1.8-py2-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于ssm+vue酒店预约及管理系统.zip

    基于ssm+vue酒店预约及管理系统.zip

    基于ssm+vue的宠物店系统.zip

    基于ssm+vue的宠物店系统.zip

    基于ssm省出口基地公共信息服务平台.zip

    基于ssm省出口基地公共信息服务平台.zip

    分子模拟技术在传统药物设计领域应用20160121.pdf

    分子模拟技术在传统药物设计领域应用20160121

    LS-201510-DS应用案例.pdf

    LS-201510-DS应用案例

Global site tag (gtag.js) - Google Analytics