襙你媽的
幹
我的時間就這樣不見了
只能說
我沒有想到BFS可以用priority_queue 對ㄚ
學到了==
def __init__(self):
self.sft = [[1,0],[-1,0],[0,1],[0,-1]]
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
thfs_row = []
thfs_col = []
# init thfs positions
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
thfs_row.append(i)
thfs_col.append(j)
# init dis matrix
dis = [[sys.maxsize]*n for _ in range(m)]
visit = [[False]*n for _ in range(m)]
q = deque()
for k in range(len(thfs_row)):
q.append((0, thfs_row[k], thfs_col[k]))
visit[thfs_row[k]][thfs_col[k]] = True
while q:
cur_dis, cur_row, cur_col = q.pop()
dis[cur_row][cur_col] = min(cur_dis, dis[cur_row][cur_col])
for i in range(4):
next_row = cur_row + self.sft[i][0]
next_col = cur_col + self.sft[i][1]
if 0 <= next_row <= m-1 and 0 <= next_col <= n-1 and
visit[next_row][next_col] is False:
q.appendleft((cur_dis+1, next_row, next_col))
visit[next_row][next_col] = True
# bfs
h = []
visit = [[False]*n for _ in range(m)]
heappush(h, (-dis[0][0], 0, 0))
while h:
cur_min_dis, cur_row, cur_col = heappop(h)
cur_min_dis = -cur_min_dis
visit[cur_row][cur_col] = True
if cur_row == m-1 and cur_col == n-1:
return cur_min_dis
for i in range(4):
next_row = cur_row + self.sft[i][0]
next_col = cur_col + self.sft[i][1]
if 0 <= next_row <= m-1 and 0 <= next_col <= n-1 and
visit[next_row][next_col] is False:
ss = min(cur_min_dis, dis[next_row][next_col])
heappush(h, (-ss, next_row, next_col))
visit[next_row][next_col] = True
return -1