Simulation volume leetcode [general] 1091 The shortest path in binary matrix

1091. Shortest path in binary matrix

To give you one n x n The binary matrix of grid in , Returns the shortest in the matrix Clear path The length of . If there is no such path , return -1 .

In a binary matrix Clear path It's a road from top left corner Cell （ namely ,(0, 0)） To The lower right corner Cell （ namely ,(n - 1, n - 1)） The path of , The path also meets the following requirements ：

The value of all cells in the path is 0 .
All adjacent cells in the path should be in 8 One of the directions Upper connection （ namely , Two adjacent cells are different from each other and share an edge or corner ）.
The length of the unblocked path Is the total number of cells that the path passes through .

Example 1：

Input ：grid = [[0,1],[1,0]]
Output ：2
Example 2：

Input ：grid = [[0,0,0],[1,1,0],[1,1,0]]
Output ：4
Example 3：

Input ：grid = [[1,0,0],[1,1,0],[1,1,0]]
Output ：-1

Tips ：

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] by 0 or 1

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        pass

    @lru_cache(None)
    def next(self,rowid,colid):
        res = []
        for row_id, col_id in ((rowid - 1, colid), (rowid, colid - 1), (rowid + 1, colid), (rowid, colid + 1),
                               (rowid - 1, colid-1), (rowid+1, colid - 1), (rowid + 1, colid+1), (rowid-1, colid + 1)):
            if 0 <= row_id < self.height and 0 <= col_id < self.width and 0==self.grid[row_id][col_id]:
                res.append([row_id, col_id])
        return res

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:return -1
        self.height = self.width = length = len(grid)
        self.grid = grid

        vis = set()
        step = 1
        now = [(0,0)]
        while now:
            next = []
            for i,j in now:
                if i==j==length-1:
                    return step
                for x,y in self.next(i,j):
                    if (x,y) not in vis:
                        vis.add((x,y))
                        next.append((x,y))
            step+=1
            now=next
        return -1


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.shortestPathBinaryMatrix(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [[[0,0,0],[1,1,0],[1,1,0]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！