aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_binary_matrix.py
blob: ee958335255e5b061c13df5a7f19e98195a1f74e (plain)
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
# 1091. Shortest Path in Binary Matrix

"""
given an n x n binary matrix 'grid', return the length of the shortest clear
path in the matrix. if there is no clear path, return -1. a clear path in a
binary matrix is a path from the top-left cell (ie. 0,0) to the bottom-right
cell (ie. n - 1, n - 1) such thatyt
- all the visited cells are of the path 0
- all the adjacent cells of the path are 8-directionally connected (ie. they
are different and they share an edge of a corner) the length of a clear path
is the number of visited cells of this path
"""


class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        if grid[0][0] or grid[n - 1][n - 1]:
            return -1
        q = [(0, 0, 1)]
        grid[0][0] = 1
        for i, j, d in q:
            if i == n - 1 and j == n - 1:
                return d
            for x, y in (
                (i - 1, j - 1),
                (i - 1, j),
                (i - 1, j + 1),
                (i, j - 1),
                (i, j + 1),
                (i + 1, j - 1),
                (i + 1, j),
                (i + 1, j + 1),
            ):
                if 0 <= x < n and 0 <= y < n and not grid[x][y]:
                    grid[x][y] = 1
                    q.append((x, y, d + 1))
        return -1


if __name__ == "__main__":
    obj = Solution()
    print(obj.shortestPathBinaryMatrix(grid=[[0, 1], [1, 0]]))
    print(obj.shortestPathBinaryMatrix(grid=[[0, 0, 0], [1, 1, 0], [1, 1, 0]]))
    print(obj.shortestPathBinaryMatrix(grid=[[1, 0, 0], [1, 1, 0], [1, 1, 0]]))