当前位置:网站首页>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 !
边栏推荐
- win10无法操作(删除、剪切)文件
- 10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
- Linux regularly backs up MySQL database
- LeetCode 739. 每日温度
- Fault, error, failure of functional safety
- E - 食物链
- Understanding of processes and threads
- [ram IP] introduction and experiment of ram IP core
- [postman] collections configuration running process
- 这些年用Keil遇到的坑
猜你喜欢
【Postman】测试(Tests)脚本编写和断言详解
Function of contenttype
sourceInsight中文乱码
Manage configuration using Nacos
把el-tree选中的数组转换为数组对象
Overview of three core areas of Mathematics: algebra
Expose the serial fraudster Liu Qing in the currency circle, and default hundreds of millions of Cheng Laolai
Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
Customize the gateway filter factory on the specified route
Embedded point test of app
随机推荐
黑猫带你学eMMC协议第10篇:eMMC读写操作详解(read & write)
Manhattan distance and Manhattan rectangle - print back font matrix
【Postman】动态变量(也称Mock函数)
Caused by:org.gradle.api.internal.plugins . PluginApplicationException: Failed to apply plugin
模拟卷Leetcode【普通】1109. 航班预订统计
Left matching principle of joint index
E - 食物链
Request forwarding and redirection
What are the test sites for tunnel engineering?
[C language] qsort function
LeetCode 731. 我的日程安排表 II
数据库隔离级别
MFC关于长字符串unsigned char与CString转换及显示问题
Buuctf-[bjdctf2020]zjctf, but so (xiaoyute detailed explanation)
「 WEB测试工程师 」岗位一面总结
Interface test: what are the components of the URL in fiddler
ESP32 ESP-IDF看门狗TWDT
Application of Lie group in gtsam
Function of activation function
B - The Suspects