主題
Description：
給定一m*n map，並給定一個query，for query[i]，從map的左上角出發，每次可以上下左右走，若query[i] <= map[j][k]則不通，若可以走則得到1分。可以走的格子能夠反覆經過。
思考：
DFS，可是想不到終止條件
BFS好像比較適合，打算直接叫GPT陪我討論
維護一個Visited矩陣，透過BFS去找鄰近可以走的地方
==
Naive的作法會TLE，所以要小動一下思路
將所有 query 先做排序，並記錄原本的 index。
這樣就能重複使用上一個query的結果了
======
思考得累了
昨天晚上開了長長的會，練習長大
感覺，如果我真的接了，接下來的自己會變成ALL WORK的無聊人
不知道自己做不做得到，熬不熬得住
我想盡力處理自己夢幻泡泡的部分，太常自我催眠了
而且如果要做，那我的論文進度要再加快，休息時間一定會再縮減，我有辦法一周只休一天嗎?或是只休2個半天?這個有難度
我覺得麻煩的點在於「我就很想接這個但我其實沒核心理由接」，我沒想清楚，或者說不夠清楚
回家跟家人聊聊吧
class Solution:
def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(grid), len(grid[0])
k = len(queries)
directions = [(-1,0), (1,0), (0,-1), (0,1)]
ans = []
def bfs(queries):
indexed_queries = sorted((val, idx) for idx, val in enumerate(queries))
answer = [0] * k
visited = [[False] * n for _ in range(m)]
heap = []
heapq.heappush(heap, (grid[0][0], 0, 0))
visited[0][0] = True
count = 0 # 目前拓展了多少格子
idx = 0 # 指向當前query
while heap and idx < k:
threshold, query_idx = indexed_queries[idx]
# 當 heap 中最小的格子 < threshold，就擴展它
while heap and heap[0][0] < threshold:
val, x, y = heapq.heappop(heap)
count += 1
for dx, dy in directions:
nx, ny = x+dx, y+dy
# 不能超出地圖範圍
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
visited[nx][ny] = True # 這邊是為了避免重複進heap
heapq.heappush(heap, (grid[nx][ny], nx, ny))
# 對所有 query[i] 值 <= threshold，填入 answer
while idx < k and indexed_queries[idx][0] <= threshold:
answer[indexed_queries[idx][1]] = count
idx += 1
# 剩下沒處理的 query（全部比目前最小值大），都填 count
while idx < k:
answer[indexed_queries[idx][1]] = count
idx += 1
return answer
ans = bfs(queries)
return ans
