首页 > 试题广场 >

游戏地图路径

[编程题]游戏地图路径

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

vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建筑、高山、河流或者其它障碍物等)，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。

数据范围： $5\le n \le 1000\$

进阶：时间复杂度 $O(n^2)\$ ，空间复杂度 $O(n^2)\$

输入描述:

第一行表示矩阵大小 n，5 第二行表示起点和终点的坐标
第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其他字母、非0数字、以及符号+、-、* 等等均表示普通可达格子，共有 n 行  n 列

输出描述:

输出最优路径的长度；若无法到达，则输出-1

示例1

输入

15
0 7 7 7
*5#++B+B+++++$3
55#+++++++###$$
###$++++++#+*#+
++$@$+++$$$3+#+
+++$$+++$+4###+
A++++###$@+$++A
+++++#++$#$$+++
A++++#+5+#+++++
+++$$#$++#++++A
+++$+@$###+++++
+###4+$+++$$+++
+#+3$$$+++$##++
+#*+#++++++#$$+
$####+++++++$##
3$+++B++B++++#5

输出

备注:

最优即最短，寻找最优路径时只能按上下左右四个方向前进。

算法知识视频讲解

Python

牛客589187471号

迷宫问题寻找最短路径，用广度优先搜索

from collections import deque
def solution():
    n = int(input().strip())
    y0, x0, y1, x1 = [int(x) for x in input().split(" ")]
    M = []
    step = 0
    flag = 0
    for _ in range(n):
        M.append([x for x in input().strip()])

    que = deque([[x0, y0]])
    M[x0][y0] = "0"
    while que:
        c = len(que)
        step += 1
        for _ in range(c):
            cur_x, cur_y = que.popleft()
            for a, b in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                next_x, next_y = cur_x + a, cur_y + b
                if next_x == x1 and next_y == y1:
                    if M[next_x][next_y] not in "0#@":
                        print(step)
                        flag = 1
                        return
                    else:
                        print(-1)
                        return
                if 0 <= next_x < n and 0 <= next_y < n and M[next_x][next_y] not in "0#@":
                    que.append([next_x, next_y])
                    M[next_x][next_y] = "0"
    if flag == 0:
        print(-1)
solution()

发表于 2021-04-09 23:20:18 回复(0)