leetcode/algorithm/LeetCode_1091_0041.py at master · txf0096/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from heapq import heappop, heappush
from typing import List


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0 or grid[0][0] == 1:
            return -1
        target = (n - 1, n - 1)

        def get_neighbors(i, j):
            return [(x, y) for x, y in
                    [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1), (i + 1, j + 1), (i - 1, j - 1), (i + 1, j - 1),
                     (i - 1, j + 1)] if 0 <= x < n and 0 <= y < n and grid[x][y] == 0]

        queue = [(0, 0)]
        visitor = set([(0, 0)])
        cnt = 1
        while queue:
            nq = []
            for i, j in queue:
                if (i, j) == target:
                    return cnt
                for x, y in get_neighbors(i, j):
                    if (x, y) not in visitor:
                        visitor.add((x, y))
                        nq += [(x, y)]
            queue = nq
            cnt += 1
        return -1

    def shortestPathBinaryMatrixAH(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0 or grid[0][0] == 1:
            return -1
        target = (n - 1, n - 1)
        heap = [(0, 1, 0, 0)]
        scores = {(0, 0): float("inf")}

        def get_neighbors(i, j):
            return [(x, y) for x, y in
                    [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1), (i + 1, j + 1), (i - 1, j - 1), (i + 1, j - 1),
                     (i - 1, j + 1)] if 0 <= x < n and 0 <= y < n and grid[x][y] == 0]

        while heap:
            f, g, i, j = heappop(heap)
            if (i, j) == target:
                return g
            if scores[(i, j)] < f:  # remove 重复的节点
                continue
            for x, y in get_neighbors(i, j):
                heuristic = max(abs(x - target[0]), abs(y - target[1]))
                ng = g + 1
                nf = heuristic + ng
                if nf < scores.get((x, y), float('inf')):
                    heappush(heap, (nf, ng, x, y))
                    scores[(x, y)] = nf

        return -1


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().shortestPathBinaryMatrix(
    [[0, 0, 0, 0, 1, 1, 1, 1, 0], [0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0, 1, 1],
     [0, 0, 1, 1, 1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 1, 0, 1, 1, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 0, 1, 0]]))