首页 > 试题广场 >

对称飞行器

[编程题]对称飞行器
  • 热度指数:3367 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小强在玩一个走迷宫的游戏,他操控的人物现在位于迷宫的起点,他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格,或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子,且每一次移动的目的地不能存在障碍物。
具体来说,设当前迷宫有  行  列,如果当前小强操控的人物位于点 ,那么关于点  中心对称的格子 满足
需要注意的是,对称飞行器最多使用次。

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


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

输入

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

输出

4

说明

一种可行的路径是用对称飞行器到达 \text (4,3) 再向上走一步,再向右走一步,然后使用一次对称飞行器到达终点。
头像 不想看论文
发表于 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> 展开全文