本文主要是介绍力扣1036.逃离大迷宫(Python题解)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目网址：

https://leetcode-cn.com/problems/escape-a-large-maze/submissions/

题目解析：

迷宫题目应该利用bfs进行解答，但是这道题目需要一点优化，给出的迷宫最大可到[1e6, 1e6]， 数目庞大，如果直接进行遍历那么肯定会超时，但是我们可以巧妙地利用这个障碍，如果没有完全封锁的话，意味着我们可以走出去，但是封锁的话能达到什么地步呐？最大只能由200个坐标被封锁，最大化的话，就是说封锁一个角落最大值为n*(n-1)//2，n是封锁的坐标，所以容我们走的步数大于这个，那么一定可以走出去。所以答案就出来了。

代码如下

class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        MAXINT = 1e6
        blocked_maze, MAX = {tuple(p) for p in blocked}, len(blocked)*(len(blocked)-1)//2

        def bfs(start, end):
            path, num, visit = [start], 0, {tuple(start)}

            while num < len(path):
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    x1, y1 = path[num][0] + dx, path[num][1] + dy
                    if 0<=x1<MAXINT and 0<=y1<MAXINT and (x1, y1) not in visit and (x1, y1) not in blocked_maze:
                        if [x1, y1] == end:
                            return True
                        path.append((x1, y1))
                        visit.add((x1, y1))
                if len(path) > MAX:
                    return True
                num += 1
            return False

        return bfs(source, target) and bfs(target, source)

这篇关于力扣1036.逃离大迷宫(Python题解)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！