图搜索 | 士兵的任务2（迷宫问题）

def in_board(x, y, n, m):
    if 0 <= x < m and 0 <= y < n:
        return True
    return False

def find_paths(graph, node, time, visited:list, n, m, queue:list, res):
    x, y = node
    visited[x][y] = 1
    for i in range(4):
        xx, yy = x+ix[i], y+iy[i]
        if in_board(xx, yy, n, m) and not visited[xx][yy]:
            if graph[xx][yy] == '3':
                queue.append((xx, yy, time+1))
                res.append(copy.deepcopy(queue))
                queue.pop()
                return
            elif graph[xx][yy] == '0':
                queue.append((xx, yy, time+1))
                find_paths(graph, (xx, yy), time+1, visited, n, m, queue, res)
                queue.pop()
            elif graph[xx][yy] == '4':
                queue.append((xx, yy, time+1))
                find_paths(graph, (xx, yy), time+1+3, visited, n, m, queue, res)
                queue.pop()
            elif graph[xx][yy] == '6':
                graph2 = copy.deepcopy(graph)
                visited2 = copy.deepcopy(visited)
                for j in range(4):
                    bump_x, bump_y = xx+ix[j], yy+iy[j]
                    if in_board(bump_x, bump_y, n, m) and graph[bump_x][bump_y] == '1':
                        graph2[bump_x][bump_y] = '0'
                        visited2[bump_x][bump_y] = 0
                queue.append((xx, yy, time+1))
                find_paths(graph2, (xx, yy), time+1, visited2, n, m, queue, res)
                queue.pop()
            elif graph[xx][yy] == '1':
                visited[xx][yy] = 1

def dfs_get_min_dis():
    n, m = input().split()
    n, m = int(n), int(m)
    graph, visited = [], [[0 for _ in range(m)]for _ in range(n)]
    si, sj = 0, 0
    for i in range(n):
        row = input().split(' ')
        graph.append(row)
        if '2' in row:
            si, sj = i, row.index('2')
            visited[si][sj] = 1
    res = []
    find_paths(node=(si,sj), queue=[], time=0, graph=graph, visited=visited, n=n, m=m, res=res)
    times = [group[-1][2] for group in res]
    print(min(times))

题目描述：

士兵在迷宫中执行任务,迷言中危机重重,他需要在在最短的时问内到达指定的位置。你可以告诉士兵他最少需要多长时问吗?输入一个nm的迷宫中,迷宫中0为路,1为墙,2为起点，3为终点,4为陷阱,6为炸弹。士兵只能向上下左右四个方向移动,如果路径上为墙,不能移动。已知每走一步需要花费1个单位的时间,走到陷阱上需要花费3个单位的时间,走到x弹上将会激活炸弹将炸弹上下右的墙炸为路。 注意点: 1、炸弹只能炸毁墙,不会炸掉陷阱 2、炸弹、陷阱只能发挥1次作用 3、迷宫为最大为25*25

4、用例保证士兵定有方法能到达终点

用时：5h