核心概念
使用二分搜搭配 BFS。
利用二分搜天數，找到 "The last day where we can still cross"。當二分搜到的該天還有路可以走則繼續往後面的天數二分搜，若沒路可以走則往前面的天數二分搜。舉個例子，假如是 3*3 的矩陣，會有九天需要確認。第一次檢查第五天是否有路可以走，如果有，則檢查第七或第八天 (取決於程式碼如何設計)；如果沒有，則檢查第二或第三天 (取決於程式碼如何設計)
BFS 則是負責遍歷所有路徑。仔細來說就是，每一層迴圈都去查找一個 raw 中各元素的上下左右是否可以走 (檢查上方是因為可能可以往上繞)。
當然，其中還有一些小細節。例如，最基礎的邊界檢查；用 set 儲存走過的格子 (如果使用 Python)，因為若 (1,1) (1,2) (1,3) 可走，(1,2) 會在檢查 (1,1) 右邊，(1,2)左邊後被新增兩次。至於用 set 是因為，set 在 Python 中是以 hashtable 形式建立，查詢是否重複時比較快；以及用遞迴實作 BFS 可能會 MLE。
程式碼執行流程
在 Solution class 中開另一個 canCross 函數處理 BFS。
在 latestDayToCross 函數中，變數 left, right 儲存二分搜的左界和右界。
執行 while 迴圈直到 left > right 或 left == right。接著，將中間值 (要檢查的天) 帶入 canCross 函數。如果回傳 True，則 left = mid + 1；如果回傳 False，則 right = mid。舉個例子，現在有 1, 2, 3, 4 天。其中，1 和 2 可以走，3 和 4 不行走。第一次 left = 1, right = 4, mid = 2；第二次 left = 3, right = 4, mid = 3 ; 第三次 left = 3, right = 3 結束。最後，回傳 right -1。減一是因為找到的那天是不能走的。
canCross 中，我們先將 cells 轉成 set 型態方便之後檢查。
變數 queue 用來儲存當前的位置，當要檢查格子時從左邊 pop 出來，達到先進先出(右進左出)；visited 用來儲存走過的格子避免重複檢查。
對於矩陣的第一層，我們獨立檢察。如果不在 water 中，就新增進 queue 和 visited 中。至於為什麼用 tuple 來儲存 r 和 c，是因為 tuple is hashable，換句話說，只有 tuple 可以新增進 set，其餘的像 list、dictionary 都不行。可能有人會看到除 add 還有一個 update 函式也可以新增資料，並且還可以將 list 當參數帶入，但新增進 set 的資料不會兩兩一對。
這裡，我們舉個例子
假如我們有一個 3*3 的矩陣，並且還在第一天的狀態。此時，當我們的程式碼檢查完第一層矩陣後 queue = [(0,0), (0,2)], visited = [(0,0), (0,2)]
接著往下走是 BFS 的 while 迴圈。這裡，我們執行到 queue 沒有東西為止
我們從 queue 中的最左邊開始取，並用 r 和 c 來存。如果 r == row - 1，代表我們已經到最後一個 row，檢查完畢，這天還是有路可以走的，回傳 True。如果還沒走到最後，則去檢查剛剛取出那點的上下左右是否可以走
以下是完整的程式碼
from collections import deque
class Solution:
def canCross(self, day: int, row: int, col: int, cells: list) -> bool:
# 建立第 day 天的水域
water = set()
for i in range(day):
water.add((cells[i][0]-1, cells[i][1]-1))
# BFS
queue = deque()
visited = set()
for c in range(col):
if (0, c) not in water:
queue.append((0, c))
visited.add((0, c))
while queue:
r, c = queue.popleft()
if r == row - 1:
return True
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < row and 0 <= nc < col
and (nr, nc) not in water
and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))
return False
def latestDayToCross(self, row: int, col: int, cells: list) -> int:
left, right = 1, (row*(col-1))+1
while left < right and left != right:
mid = (left + right ) // 2
if self.canCross(mid, row, col, cells):
left = mid + 1 # 還能走，試更晚的天數
else:
right = mid # 走不通，試更早的天數
return left-1
