zoj 2110 Tempter of the Bone(DFS+奇偶剪枝及优化操作)

2023-11-08 12:08

本文主要是介绍zoj 2110 Tempter of the Bone(DFS+奇偶剪枝及优化操作),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110

2、题目大意:

Tempter of the Bone

           


           

Time Limit: 2 Seconds                                    Memory Limit: 65536 KB                           

           


           

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

 

2、AC代码:

#include<stdio.h>
#include<math.h>
char map[9][9];
int n,m,sx,sy,ex,ey,t;
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int flag;
void DFS(int ssx,int ssy,int cnt)
{//此代码会导致返回的上一结点,不能通过flag=1直接返回
//    if(ssx==ex && ssy==ey && cnt==t)
//    {
//        flag=1;
//        return;
//    }if(ssx==ex && ssy==ey && cnt==t)flag=1;if(flag)return;if(ssx<=0 || ssx>n || ssy<=0 || ssy>m)return;int tmp=t-cnt-fabs(ex-ssx)-fabs(ey-ssy);if(tmp<0 || tmp%2!=0)//奇偶剪枝return;for(int i=0;i<4;i++){int tx=ssx+dir[i][0];int ty=ssy+dir[i][1];if( map[tx][ty]!='X'){map[tx][ty]='X';DFS(tx,ty,cnt+1);map[tx][ty]='.';}}return ;
}
int main()
{while(scanf("%d%d%d",&n,&m,&t)!=EOF){getchar();int wall=0;if(n==0 && m==0 && t==0)break;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S'){sx=i;sy=j;}else if(map[i][j]=='D'){ex=i;ey=j;}else if(map[i][j]=='X')wall++;}getchar();}if(n*m-wall<=t)//优化操作,如果能走的个数小,直接返回NOprintf("NO\n");else{flag=0;map[sx][sy]='X';DFS(sx,sy,0);if(flag)printf("YES\n");elseprintf("NO\n");}}return 0;
}


 

这篇关于zoj 2110 Tempter of the Bone(DFS+奇偶剪枝及优化操作)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369747

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语