石碑之谜:滚动机关

描述

在蒙德和璃月的边界地带,有一个被遗忘的神庙,里面有一个奇怪的机关:滚动石碑。小熊必须操作这个1×1×2的长方体石碑,使其通过不同的地面环境,最终放置到神秘的符号“O”上,以解开通往宝藏的大门。

石碑可以有三种放置形式:

  • 立在地面上(1×1的面接触地面)。
  • 横躺在地面上(1×2的面接触地面),似乎是为了休息或避开某些地面的损害。
  • 竖趟在地面上(1×2的面接触地面)

地图是一个N行M列的矩阵,代表着充满未知的遗迹内部:

  • 正常的地面由“.”表示,平坦且安全。
  • 易碎的地面用“E”标识,石碑不能以全部重量压在这种地面上,特别是立着时。
  • 不能通过的地面用“#”表示,这可能是古代结界或坍塌的部分。
  • 起点用“X”表示,石碑的初始位置。
  • 终点由“O”标识,是需要将石碑立在其上的目标位置。

小熊通过上下左右四个方向键来控制石碑沿边缘滚动90°。在整个探索过程中,石碑不能碰到不可通过的地面,也不能在易碎地面上以1×1的面立着。

地图上的“X”可能标识一个或两个相邻的位置,显示石碑是初始时是立着还是躺着的状态。

小熊的任务是以最少的步数,将石碑正确地立在“O”上,揭开这片古老土地的秘密。

image.png

image.png

image.png

输入

输入包含多组测试用例。

对于每个测试用例,第一行包括两个整数N和M。

接下来N行用来描述地图,每行包括M个字符,每个字符表示一块地面的具体状态。

当输入用例N=0,M=0时,表示输入终止,且该用例无需考虑。

数据范围

3≤N,M≤500

输出

对于每个测试用例,输出一个整数,表示小熊将石碑从起点推到目标点所需的最少步数。如果石碑无法成功地被推至目标点,则输出"Impossible"。

每个测试用例的结果输出在单独的一行。

输入样例 1 
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例:

10

代码实现:

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=510;
char area[N][N];
int dist[N][N][3];
int n,m;
struct stone
{//立0    横1    竖2int x,y,st;stone(int a,int b,int c){x=a,y=b,st=c;}stone():x(0),y(0),st(0){};
};
stone start,target;int dxyz[4][3][3]={//dxyz[i][st][x,y,st]{{-2,0,2},{-1,0,1},{-1,0,0}},//向上{{0,-2,1},{0,-1,0},{0,-1,2}},//向左{{1,0,2},{1,0,1},{2,0,0}},//向下{{0,1,1},{0,2,0},{0,1,2}}//向右};
stone movestone(stone &p,int i)
{int x=p.x+dxyz[i][p.st][0];int y=p.y+dxyz[i][p.st][1];int z=dxyz[i][p.st][2];return stone(x,y,z);
}
bool isInside(int i,int j)
{return (i>=0&&j>=0&&i<n&&j<m);
}
bool isValid(stone s)
{if(!isInside(s.x,s.y)||area[s.x][s.y]=='#')return false;if(s.st==1&&(!isInside(s.x,s.y+1)||area[s.x][s.y+1]=='#'))return false;if(s.st==2&&(!isInside(s.x+1,s.y)||area[s.x+1][s.y]=='#'))return false;if(s.st==0&&area[s.x][s.y]=='E')return false;return true;
}
bool isVisited(stone t)
{return dist[t.x][t.y][t.st]!=-1;
}
int bfs(stone& s)
{queue<stone> q;q.push(s);dist[s.x][s.y][s.st]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){stone p=movestone(t,i);if(!isValid(p))continue;if(!isVisited(p)){dist[p.x][p.y][p.st]=dist[t.x][t.y][t.st]+1;q.push(p);if(p.x==target.x&&p.y==target.y&&p.st==target.st)return dist[p.x][p.y][p.st];}}}return -1;
}
int main()
{while(cin>>n>>m&&n){memset(area,'#',sizeof area);memset(dist,-1,sizeof dist);for(int i=0;i<n;i++)cin>>area[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++){char t=area[i][j];if(t=='X'){start.x=i,start.y=j,start.st=0;area[i][j]='.';if(area[i][j+1]=='X')start.st=1,area[i][j+1]='.';if(area[i+1][j]=='X')start.st=2,area[i+1][j]='.';}if(t=='O')target.x=i,target.y=j,target.st=0;}int res=bfs(start);if(res==-1)cout<<"Impossible"<<endl;else cout<<res<<endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328428.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何使用JMeter测试导入接口/导出接口?

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号&#xff1a;互联网杂货铺&#xff0c;回复1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 今天上班&#xff0c;被开发问了一个问题&#xff1a;JM…

OpenHarmony标准设备应用开发(二)——布局、动画与音乐

本章是 OpenHarmony 标准设备应用开发的第二篇文章。我们通过知识体系新开发的几个基于 OpenHarmony3.1 Beta 标准系统的样例&#xff1a;分布式音乐播放、传炸弹、购物车等样例&#xff0c;分别介绍下音乐播放、显示动画、动画转场&#xff08;页面间转场&#xff09;三个进阶…

TypeScript学习日志-第二十四天(webpack构建ts+vue3)

webpack构建tsvue3 一、构建项目目录 如图&#xff1a; shim.d.ts 这个文件用于让ts识别.vue后缀的 后续会说 并且给 tsconfig.json 增加配置项 "include": ["src/**/*"] 二、基础构建 安装依赖 安装如下依赖&#xff1a; npm install webpack -D …

基于网络爬虫技术的网络新闻分析(二)

目录 2 系统需求分析 2.1 系统需求概述 2.2 系统需求分析 2.2.1 系统功能要求 2.2.2 系统IPO图 2.2 系统非功能性需求分析 3 系统概要设计 3.1 设计约束 3.1.1 需求约束 3.1.2 设计策略 3.1.3 技术实现 3.3 模块结构 3.3.1 模块结构图 3.3.2 系统层次图 3.3.3…

VRRP虚拟路由器冗余协议

VRRP概述 VRRP是什么 VRRP&#xff1a;虚拟路由器冗余协议过把几台路由设备联合组成一台虚拟的路由设备&#xff0c;将虚拟路由设备的IP地址作为用户的默认网关实现与外部网络通信当网关设备发生故障时&#xff0c;VRRP能够选举新的网关设备承担数据流量&#xff0c;从而保障…

2024软件测试必问的常见面试题1000问!

01、您所熟悉的测试用例设计方法都有哪些&#xff1f;请分别以具体的例子来说明这些方法在测试用例设计工作中的应用。 答&#xff1a;有黑盒和白盒两种测试种类&#xff0c;黑盒有等价类划分法&#xff0c;边界分析法&#xff0c;因果图法和错误猜测法。白盒有逻辑覆盖法&…

大模型日报2024-05-15

大模型日报 2024-05-15 大模型资讯 OpenAI推出全新AI模型GPT-4o&#xff0c;具备文本、图像和音频处理能力 摘要: OpenAI公司继ChatGPT后&#xff0c;最新推出了名为GPT-4o的AI模型。这一模型不仅能够理解和生成文本&#xff0c;还新增了图像和音频的解释及生成功能。GPT-4o作为…

【Web】CTFSHOW 单身杯 题解

目录 web签到 easyPHP 姻缘测试 web签到 用data协议包含php标签闭合 payload: filedata://text/plain,<?php system($_GET[1]);?>>?;)]1[TEG_$(metsys php?<,nialp/txet//:atadeasyPHP 一眼awk命令执行 payload: cmdawk&param{system("ta…

基于单片机的智能安防系统设计(32+4G+WIFI版)-设计说明书

设计摘要&#xff1a; 本设计基于STM32单片机&#xff0c;旨在实现一个智能安防系统&#xff0c;主要包括烟雾和温度传感器、人体红外传感器、显示屏、按键、4G模块和WiFi模块等组件。通过这些组件的协作&#xff0c;实现了火灾检测、入侵监测、状态显示、用户交互和远程通信等…

静态NAT

哈喽&#xff01;各位小伙伴们好久不见&#xff0c;最近由于工作的原因断更了一段时间&#xff0c;不过最近我都会把这些给补上&#xff0c;今天我们来学习一个简单的知识——静态NAT转换。 第一章 什么是NAT技术&#xff1f; 网络地址转换技术NAT&#xff08;Networ…

【RSGIS数据资源】2001-2021 年亚洲季风区主要国家作物种植制度数据集

文章目录 1. 数据集概况2. 数据格式3. 文件名命名规则4. 数据生产服务单位5. 元数据6. 数据引用与参考文献引用 1. 数据集概况 2001-2021 年亚洲季风区主要国家作物种植制度数据集&#xff08;ACIA500&#xff09;是结合MODIS 影像和现有的土地利用等多源数据&#xff0c;基于…

_pickle.UnpicklingError: STACK_GLOBAL requires str

导致这个报错的原因是我跑yolo的时候修改数据集了&#xff0c;里面的label.cache没有删除&#xff0c;咱只要删除掉缓存就行&#xff01;&#xff01; 我这里是已经删除掉了&#xff0c;所以图片里面没有&#xff0c;一般就是在箭头所示位置有.cache文件的

Docker常用镜像安装

1. mysql 1.1 安装 获取镜像 docker pull mysql:8.0.30创建文件挂载目录 创建容器并运行 docker run -p 3306:3306 --name mysql8 \ -v /home/docker/mysql8/log:/var/log/mysql \ -v /home/docker/mysql8/data:/var/lib/mysql \ -v /home/docker/mysql8/mysql-files:/va…

【Linux】系统登录,调用shell,shell配置文件,shell命令,特殊符号,shell快捷键,Linux运行级别,解决无限登录问题,修改提示符

目录 Linux系统的登录方式 以及 调用shell Linux shell 以及 shell配置文件 shell 命令 shell 特殊符号 shell 快捷键 Linux操作系统运行级别 单用户模式下解决无限登录问题 centos7修改命令行提示符 PS1 补充、centos7没有滚动条 Linux系统的登录方式 以及 调用shell…

Python进度条工具——tqdm

原文链接&#xff1a;http://www.juzicode.com/python-note-tqdm 在安装Python库文件的时候我们经常可以看到这种进度条&#xff1a; 其实Python库中就自带了现成的工具库——tqdm。 tqdm读起来比较拗口&#xff0c;它是从“进程”的阿拉伯语taqaddum简化而来。 安装tqdm 使用…

es 分词器(五)之elasticsearch-analysis-jieba 8.7.0

es 分词器&#xff08;五&#xff09;之elasticsearch-analysis-jieba 8.7.0 今天咱们就来讲一下es jieba 8.7.0 分词器的实现&#xff0c;以及8.x其它版本的实现方式&#xff0c;如果想直接使用es 结巴8.x版本&#xff0c;请直接修改pom文件的elasticsearch.version版本号即可…

OpenCV Radon变换探测直线(拉东变换)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 Radon变换可以将原始图像中直线特征的处理问题转化为变换域图像中对应点特征的处理问题,其中对应特征点的横坐标表示原始图像的旋转角度,一般来讲原始图像中的噪声不会分布在直线的特征上。因此,Radon变换在探测…

Spring Cloud Alibaba 网关 Gateway 集成(7)

项目的源码地址 Spring Cloud Alibaba 工程搭建&#xff08;1&#xff09; Spring Cloud Alibaba 工程搭建连接数据库&#xff08;2&#xff09; Spring Cloud Alibaba 集成 nacos 以及整合 Ribbon 与 Feign 实现负载调用&#xff08;3&#xff09; Spring Cloud Alibaba Ribbo…

网络 | 应用层-websocket协议概述与握手过程解析

背景&#xff1a;这里为了实现消息实时传输决定引入websocket协议。 不管是发送消息还是接收消息&#xff0c;都需要实时传输&#xff0c;张三发给李四&#xff0c;李四立马就能收到&#xff0c;基于HTTP实现是有些困难的。 但轮询方式也带来了一些问题 1、消耗更多系统资源&…

【Shell脚本】Shell编程之数组

目录 一.数组 1.基本概念 2.定义数组的方法 2.1.方法一 2.2.方法二 2.3.方法三 2.4.方法四 2.5.查看数组长度 2.6.查看数组元素下标 3.数组分片 4.数组字符替换 4.1.临时替换 4.2.永久替换 5.数组删除 5.1.删除某个下标 5.2.删除整组 6.数组遍历和重新定义 7…