襙你媽的 幹 我的時間就這樣不見了 只能說 我沒有想到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 -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 114.137.230.241 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1715782915.A.AAA

推 JIWP: 別卷了 05/15 22:24

→ osopopototo: 糞肏題目 05/15 22:32

推 SecondRun: 大師 教我 05/15 22:33

→ DJYOSHITAKA: 趕緊看安紗 幸好我有早點看 05/15 22:35

→ oinishere: 大師 05/15 22:44

推 silberger: 包養真心珍惜友誼情感。 05/15 22:44

→ sustainer123: 教我+1 05/15 22:48