热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

UESTC_王之迷宫2015UESTCTrainingforSearchAlgorithm&String

2015UESTCTrainingforSearchAlgori

A - 王之迷宫

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

王被困在了一个3维的迷宫中,他很想逃离这个迷宫回去当学霸,你能帮助他么? 由于王很仁慈,他悄悄地告诉你,本题读入迷宫的每一行时,要用scanf("%s"...) ......

Input

多组测试数据,对于每组测试数据,有三个整数 L,R,C0<l,r,c30)。

L代表迷宫的高度,RC分别代表每一层的行和列。

接下来是LR×C的矩阵,矩阵包含4种字符(S,E,.,#),S代表王的初始位置,E代表出口,#代表障碍。.代表能通过的地方。

每一层之后有一个空行。

L=R=C=0时,输入中断。

Output

如果可以逃离迷宫,按下列格式输出最短时间:

Escaped in x minute(s). (x表示逃离迷宫的最短时间, 走一步花费一昏钟)

否则,输出:

Trapped!

Sample input and output

Sample InputSample Output
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
Escaped in 11 minute(s).
Trapped!

解题报告:

 简单bfs,直接跑就完了

#include 
#include 
#include 
#include 
using namespace std;
char g[40][40][40];
bool vis[40][40][40];
int l,r,c;
int dir[6][3] = {-1,0,0,1,0,0,0,-1,0,0,1,0,0,0,-1,0,0,1};
typedef struct status
{
  int x,y,z,step;
  status(const int &x,const int &y,const int &z,const int &step)
   {
         this->x  = x , this->y = y, this->z = z ,this->step = step;
   }
};

queueq;
int tarx,tary,tarz;

bool judge(int x,int y,int z)
{
   if (g[z][x][y] == # || x >= r || x <0 || y >= c || y <0 || z >= l || z <0)
    return false;
   return true;
}

int bfs()
{
   while(!q.empty())
    {
        status ns = q.front();q.pop();
        if (ns.x == tarx && ns.y == tary && ns.z == tarz)
         return ns.step;
        int x = ns.x , y = ns.y , z = ns.z , step = ns.step;
        for(int i = 0 ; i <6 ; ++ i)
         {
             int newx = x + dir[i][0];
             int newy = y + dir[i][1];
             int newz = z + dir[i][2];
             if(!judge(newx,newy,newz) || vis[newx][newy][newz])
              continue;
             vis[newx][newy][newz] = true;
             q.push(status(newx,newy,newz,step+1));
         }
    }
   return -1;
}

int main(int argc,char *argv[])
{
  while(scanf("%d%d%d",&l,&r,&c)  && l )
   {
         for(int i = 0 ; i  i)
          for(int j = 0 ; j  j)
           scanf("%s",g[i][j]);
         int stx,sty,stz;
         for(int i = 0 ; i  i)
          for(int j = 0 ; j  j)
           for(int k = 0 ; k  k)
            {
                if (g[i][j][k] == S)
                 stx = j,sty = k,stz = i;
                if (g[i][j][k] == E)
                 tarx = j,tary = k , tarz = i;
         }
      while(!q.empty())
       q.pop();
      memset(vis,false,sizeof(vis));
      vis[stx][sty][stz] = true;
      q.push(status(stx,sty,stz,0));
      int ans = bfs();
      if (ans != -1)
       printf("Escaped in %d minute(s).\n",ans);
      else
       printf("Trapped!\n");
   }
  return 0;
}

,mamicode.com" target="_blank">UESTC_王之迷宫 2015 UESTC Training for Search Algorithm & String


推荐阅读
  • 本文介绍了OC学习笔记中的@property和@synthesize,包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 在说Hibernate映射前,我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象,以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • 动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤,包括划分阶段、选择状态、决策和状态转移方程,并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中,在以后尽可能多地利用这些子问题的解,从而提高算法的效率。 ... [详细]
  • 本文详细介绍了GetModuleFileName函数的用法,该函数可以用于获取当前模块所在的路径,方便进行文件操作和读取配置信息。文章通过示例代码和详细的解释,帮助读者理解和使用该函数。同时,还提供了相关的API函数声明和说明。 ... [详细]
  • 本文介绍了闭包的定义和运转机制,重点解释了闭包如何能够接触外部函数的作用域中的变量。通过词法作用域的查找规则,闭包可以访问外部函数的作用域。同时还提到了闭包的作用和影响。 ... [详细]
  • HDU 2372 El Dorado(DP)的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法,通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • Mac OS 升级到11.2.2 Eclipse打不开了,报错Failed to create the Java Virtual Machine
    本文介绍了在Mac OS升级到11.2.2版本后,使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题,并提供了解决方法。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • 《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估,包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库,可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n),通过随机取出长度为m的子串作为模式P,在文本T中进行匹配,统计平均复杂度。对于成功和失败的匹配分别进行测试,分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • Java验证码——kaptcha的使用配置及样式
    本文介绍了如何使用kaptcha库来实现Java验证码的配置和样式设置,包括pom.xml的依赖配置和web.xml中servlet的配置。 ... [详细]
  • 本文介绍了C#中生成随机数的三种方法,并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法,但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数,进一步突显了这个问题。文章指出,随机数生成在任何编程语言中都是必备的功能,但Random类生成的随机数并不可靠。最后,提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]
  • JavaSE笔试题-接口、抽象类、多态等问题解答
    本文解答了JavaSE笔试题中关于接口、抽象类、多态等问题。包括Math类的取整数方法、接口是否可继承、抽象类是否可实现接口、抽象类是否可继承具体类、抽象类中是否可以有静态main方法等问题。同时介绍了面向对象的特征,以及Java中实现多态的机制。 ... [详细]
author-avatar
榜榜爱打球
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有