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

相关文章

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

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

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