当前位置:网站首页>Simulation volume leetcode [general] 1091 The shortest path in binary matrix
Simulation volume leetcode [general] 1091 The shortest path in binary matrix
2022-07-06 06:17:00 【Encounter simulation volume】
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 !
边栏推荐
- ICLR 2022 spotlight | analog transformer: time series anomaly detection method based on correlation difference
- Digital triangle model acwing 1015 Picking flowers
- Fault, error, failure of functional safety
- Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
- 数学三大核心领域概述:代数
- Amazon Engineer: eight important experiences I learned in my career
- LeetCode 1200. 最小绝对差
- 模拟卷Leetcode【普通】1219. 黄金矿工
- Significance of unit testing
- Application du Groupe Li dans gtsam
猜你喜欢
isam2运行流程
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Pat (Grade B) 2022 summer exam
B - The Suspects
Function of contenttype
Selenium source code read through · 9 | desiredcapabilities class analysis
E - food chain
Database - current read and snapshot read
LeetCode 729. 我的日程安排表 I
Fault, error, failure of functional safety
随机推荐
Online and offline problems
Cannot create PoolableConnectionFactory (Could not create connection to database server. 错误
数据库隔离级别
[postman] the monitors monitoring API can run periodically
LeetCode 732. 我的日程安排表 III
PAT(乙级)2022年夏季考试
Interface test: what are the components of the URL in fiddler
【C语言】字符串左旋
Software test interview questions - Test Type
CoordinatorLayout+NestedScrollView+RecyclerView 上拉底部显示不全
E - 食物链
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
Redis 核心技术与实战之 基本架构:一个键值数据库包含什么?
Manhattan distance sum - print diamond
GTSAM中ISAM2和IncrementalFixedLagSmoother说明
模拟卷Leetcode【普通】1143. 最长公共子序列
Luogu p1460 [usaco2.1] healthy Holstein cows
模拟卷Leetcode【普通】1062. 最长重复子串
单元测试的意义
MySQL之基础知识