首页 > 试题广场 >

对称飞行器

[编程题]对称飞行器

热度指数：3501 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小强在玩一个走迷宫的游戏，他操控的人物现在位于迷宫的起点，他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格，或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子，且每一次移动的目的地不能存在障碍物。
具体来说，设当前迷宫有 $\mathit n$ 行 $\mathit m$ 列，如果当前小强操控的人物位于点 $\mathit A(x,y)$ ，那么关于点 $\mathit A$ 中心对称的格子 $\mathit B(x',y')$ 满足 $\mathit x+x'=n+1$ 且 $\mathit y+y'=m+1$ 。
需要注意的是，对称飞行器最多使用 $\text 5$ 次。

输入描述:

第一行两个空格分隔的正整数  ，分别代表迷宫的行数和列数。
接下来  行 每行一个长度为  的字符串来描述这个迷宫。
其中
 代表通路。
 代表障碍。
 代表起点。
 代表终点。
保证只有一个  和 一个  。

输出描述:

仅一行一个整数表示从起点最小花费多少时间单位到达终点。
如果无法到达终点，输出  。

示例1

输入

4 4
#S..
E#..
#...
....

输出

说明

一种可行的路径是用对称飞行器到达  再向上走一步，再向右走一步，然后使用一次对称飞行器到达终点。

算法知识视频讲解

不想看论文

发表于 2022-03-24 12:11:01

java版 BFS 每一个位置下一步都有五种选择，上、下、左、右或乘飞行器，我们只需遍历每一种可行的路径，并记录从起点到该点的路径长度。取所有能到达终点的路径长度的最小值。 import java.util.*; public class Main { public static voi 展开全文

wolverine12138

发表于 2021-12-29 22:40:41

从一个节点出发，搜索最短路径，选择广度优先搜索，核心在维护一个移动步数（深度）不减的队列；过程中每个节点只会入队列一次，入队列后将其标记，避免重复无效的入队操作。 #include<iostream> #include<vector> #include<queue> 展开全文

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师阿里巴巴测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

28条回答 103收藏 8461浏览

通过挑战的用户

古巴比伦王

2023-03-14 15:47:35
__baymax__

2023-03-13 22:53:55
一枚小学渣

2022-12-07 01:48:31
牛客90130...

2022-12-02 18:14:27
握爪

2022-11-25 12:59:25

对称飞行器

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题