首页 > 试题广场 >

对称飞行器

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

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


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

输入

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

输出

4

说明

一种可行的路径是用对称飞行器到达 \text (4,3) 再向上走一步，再向右走一步，然后使用一次对称飞行器到达终点。
算法知识视频讲解
添加回答
Python
徐良期头像 徐良期
class state():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.g = 0
        self.h = 0
        self.f = 0
        self.fly = 5

    def __eq__(self, other):
        if self.x == other.x and self.y == other.y and self.fly == other.fly:
            return True
        else:
            return False

    def __hash__(self):
        return hash((self.x, self.y, self.fly))

    def __lt__(self, other):
        if self.f < other.f:
            return True
        elif self.f == other.f and self.g < other.g:
            return True
        else:
            return False
     

input_1 = input().split()
row = int(input_1[0])
column = int(input_1[1])
map = []
flag = 0
start = []
goal = []
for i in range(row):
    data = input()
    if flag != 2:
        for j in range(column):
            if data[j] == "S":
                start = (i, j)
                flag += 1
            elif data[j] == "E":
                goal = (i, j)
                flag += 1
    map.append(data)

def compute_h(point1):  ##曼哈顿距离作为启发值
    return abs(point1[0] - goal[0]) + abs(point1[1] - goal[1])

def get_neighbors(current):  ###找上下左右和飞行对应的邻居节点
    neighbors = []
    if current.x + 1 < row:
        if map[current.x + 1][current.y] != "#":
            neighbor = state(current.x + 1, current.y)
            neighbor.fly = current.fly
            neighbors.append(neighbor)
    if current.x - 1 >= 0:
        if map[current.x - 1][current.y] != "#":
            neighbor = state(current.x - 1, current.y)
            neighbor.fly = current.fly
            neighbors.append(neighbor)
    if current.y + 1 < column:
        if map[current.x][current.y + 1] != "#":
            neighbor = state(current.x, current.y + 1)
            neighbor.fly = current.fly
            neighbors.append(neighbor)
    if current.y - 1 >= 0:
        if map[current.x][current.y - 1] != "#":
            neighbor = state(current.x, current.y - 1)
            neighbor.fly = current.fly
            neighbors.append(neighbor)

    if current.fly > 0:
        x = row - 1 - current.x
        y = column - 1 - current.y
        if map[x][y] != "#":
            neighbor = state(x, y)
            neighbor.fly = current.fly - 1
            neighbors.append(neighbor)
    return neighbors

start_node = state(start[0], start[1])
start_node.h = compute_h(start)
start_node.f = start_node.g + start_node.h
g_score = {start_node:0}
open_set = set()
open_set.add(start_node)
closed_set = set()
while open_set:
    current = min(open_set)
    if (current.x, current.y) == goal:  ##终点判断
        print(current.g)
        break
    open_set -= {current}
    closed_set |= {current}
    neighbors  = get_neighbors(current)
    for neighbor in neighbors:  ##找邻居节点
        if neighbor in closed_set:  ##如果以前扩展过该节点，这次直接跳过
            continue
        else:
            if neighbor not in open_set:  ##以前没扩展过该节点且不再OPEN中，那么直接加入
                neighbor.g = current.g + 1
                neighbor.h = compute_h([neighbor.x, neighbor.y])
                neighbor.f = neighbor.g + neighbor.h
                open_set |= {neighbor}  
                g_score[neighbor] = current.g + 1
            else:        ##以前没扩展过该节点但是在OPEN中，通过g值判断哪一个到达该点花费更少
                if g_score[neighbor] > current.g + 1:  ##如果新的点花费更少，那么替换一下
                    open_set -= {neighbor}
                    neighbor.g = current.g + 1
                    neighbor.h = compute_h([neighbor.x, neighbor.y])
                    neighbor.f = neighbor.g + neighbor.h
                    open_set |= {neighbor}
                    g_score[neighbor] = current.g + 1
标准的A*流程，但是第五个始终过不了，标准答案是58结果输出60，问了AI也说这个没问题，有大佬知道哪有问题吗？
发表于 2025-05-22 10:11:51 回复(0)
Python
牛客777207027号头像 牛客777207027号

BFS

from collections import deque

n, m = map(int, input().split())
migong = [input() for _ in range(n)]
S = (0, 0), 0
E = (0, 0)
for i, row in enumerate(migong, 1):
    for j, col in enumerate(row, 1):
        if col == "S":
            S = (i, j), 0
        if col == "E":
            E = (i, j)
q = deque([S])
direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
isvisited = set([S[0]])


def move(pos: tuple[tuple[int, int], int], dir: tuple[int, int]):
    (x, y), _ = pos
    dx, dy = dir
    return (x + dx, y + dy), _


def jmp(pos: tuple[tuple[int, int], int]):
    (x, y), _ = pos
    return (n + 1 - x, m + 1 - y), _ + 1


def check(pos: tuple[tuple[int, int], int]):
    (x, y), times = pos
    return (
        1 <= x <= m
        and 1 <= y <= n
        and migong[x - 1][y - 1] != "#"
        and times <= 5
        and (x, y) not in isvisited
    )


# print(migong, E, S)

cnt = 0
success = False
while q:
    l = len(q)
    for _ in range(l):
        t = q.pop()
        # print(t)
        if t[0] == E:
            print(cnt)
            success = True
            break
        for j in direction:
            tt = move(t, j)
            # print(tt)
            if check(tt):
                # print(tt)
                isvisited.add(tt[0])
                q.appendleft(tt)

        jmpt = jmp(t)
        # print(jmpt)
        if check(jmpt):
            q.appendleft(jmpt)
            isvisited.add(jmpt[0])
    cnt += 1
if not success:
    print(-1)
"""
4 4
#S..
E#..
#...
....
"""
发表于 2021-05-08 10:43:18 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
3条回答 8462浏览

热门推荐

通过挑战的用户

相关试题

对称飞行器

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号