高考加油!
带好证件!

带传送门的迷宫

2021-04-01 大聪明 0评论 84 1喜欢

题目描述

给定一个迷宫,找到最快从起点到达重点的路径所需要的步数。 假设迷宫如下,假定左上角坐标为(0, 0),右下角坐标为(3, 2)

1 0 -1 1

-2 0 -1 -3

2 2 0 0

-2是迷宫的起点,坐标为(0, 1)

-3是迷宫的终点,坐标为(3, 1)

-1代表障碍物,不能行走

1和2代表传送门,传送门门由正整数标示,只会成对出现。站在传送门上,能仅用一步就传送到相同

数字的另一个传送i门的位置: 1只能传送到1, 2只能传送到2。站在传送门上也可以选择不传送。

从起点到终点有若干种走法,举例如下:

(0,1)->(1,1)->(1,2)->(2,2)->(3,2)->(3, 1),共花费5步

或者

(0,1)->(0, 0) -传送> (3,0)->(3,1),共花费3步 经检验3步是所需的最少步数,最后结果返回3。

输入描述

每一行输入都是用空格隔开的整数

第一行给出迷宫地图的长和宽,均为正整数

之后每一行的每一个数字,都代表迷宫的一格

-2表示起点,-3表示终点,-1表示不可通过的障碍物,0表示可通过的道路,大于0的正整数代表传送门,并且保证成对出现,在传送门上,可以仅用一步传送到另一一个相同数字的传送门]的位置。

输出描述

输出最少要多少步能够从起点走到终点。

输出-1如果没有任何办法从起点走到终点。

测试用例

input

4 3

1 0 -1 1

-2 0 -1 -3

2 2 0 0

output

3

解释

在数据输入时就对数据做预处理

关键处已做注释

代码

class Node:
    def __init__(self, x, y, v):
        self.x = x
        self.y = y
        self.v = v


def dfs(point, depth):
    global minstep
    f = 0
    if point.v == -3:
        # 到达终点
        if depth < minstep:
            minstep = depth
        return depth
    vis[point.x][point.y] = 1
    for i in range(4):
        # 上下左右递归
        x = point.x + direction[i][0]
        y = point.y + direction[i][1]
        if x < 0 or x >= n or y < 0 or y >= m:
            # 越界
            continue
        if vis[x][y] == 1 or arr_map[x][y] == -1:
            # 已访问过或障碍物
            continue
        node = Node(x, y, arr_map[x][y])
        vis[x][y] = 1
        if node.v > 0:
            for s in send:
                if s.v == node.v:
                    if s.x != node.x or s.y != node.y:
                        # 传送门
                        f = dfs(s, depth+2)
                        # 迭代完事回来之后要重新从这里出发,要把访问标识是为未访问
                        vis[x][y] = 0
        else:
            f = dfs(node, depth+1)
            # 迭代完事回来之后要重新从这里出发,要把访问标识是为未访问
            vis[x][y] = 0
    return f


m, n = list(map(int, input().split()))
minstep = float('inf')
arr_map = []
vis = [[0 for i in range(m)] for i in range(n)]
send = []
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # 上下左右
for i in range(n):
    line = list(map(int, input().split()))
    arr_map.append(line)
    for j in range(m):
        if line[j] == -2:
            # 起点
            start = Node(i, j, -2)
        if line[j] == -3:
            # 终点
            end = Node(i, j, -3)
        if line[j] > 0:
            # 传送门
            p = Node(i, j, line[j])
            send.append(p)

dfs(start, 0)
if minstep == float('inf'):
    print(-1)
else:
    print(minstep)


"""
4 3
1 0 -1 1
-2 0 -1 -3
2 2 0 0

4 3
0 1 -1 0
-2 0 -1 -3
2 1 0 2

4 3
0 1 -1 0
-2 0 -1 -3
0 1 -1 0

"""

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top