Python教程

力扣1036.逃离大迷宫(Python题解)

本文主要是介绍力扣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题解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!