ETH官方钱包

前往
大廳
主題

LeetCode - 1036. Escape a Large Maze 解題心得

Not In My Back Yard | 2023-10-29 12:00:08 | 巴幣 0 | 人氣 138

題目連結(jié):


題目意譯:
現(xiàn)在有一個一百萬乘一百萬的網(wǎng)格於 XY 平面,而每一個格子的座標則表為 (x, y)(譯注:左下角為 (0, 0),右上角為 (999999, 999999)。是的,原文沒寫。)

我們一開始位於 source = [sx, sy] 這個格子(以上面的表示法,即 (sx, sy))而我們想要抵達 target = [tx, ty] 這個格子(以上面的表示法,即 (tx, ty))。而網(wǎng)格上也存在著被阻擋的格子們 blocked,其中每個 blocked[i] = [xi, yi] 代表著位於 (xi, yi) 上的格子是被阻擋住的。

在每一步之中,我們可以往北、東、南或是西方移動一格(譯注:即分別往 +Y 、 +X 、 -Y 和 -X 方向。個人是不喜歡用東西南北表示),前提是該格並沒有位於陣列 blocked 中。而同時我們也不被允許走出網(wǎng)格範圍外。

回傳真(True)若且唯若可以經(jīng)過若干步合法的步數(shù)之後從 source 抵達 target。

限制:
0 ≦ blocked.length ≦ 200
blocked[i].length == 2
0 ≦ xi, yi < 10 ^ 6
source.length == target.length == 2
0 ≦ sx, sy, tx, ty < 10 ^ 6
source != target
保證 source 和 target 不會被阻擋起來。



範例測資:
範例 1:
輸入: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
輸出: false
解釋: target 那個格子是無法從 source 抵達的,因為我們壓根就沒辦法移動。
不能往北(+Y)或東方(+X)移動,因為那些格子被阻擋住了。
不能往南(-Y)或西方(-X)移動,因為會超過網(wǎng)格範圍。

範例 2:
輸入: blocked = [], source = [0,0], target = [999999,999999]
輸出: true
解釋: 因為不存在任何被阻擋住的格子,因此是可以從 source 抵達 target 的。


解題思維:
從 source 和 target 各自進行一次深度優(yōu)先搜尋(Depth First Search,DFS)(廣度優(yōu)先搜尋(Breadth First Search,BFS)也行),而只要雙方都可以滿足以下條件之一,則代表我們可以從 source 抵達 target:
假設(shè)起點為 X 、 Y,而現(xiàn)在走到了 x 、 y,而如果 |X - x| + |Y - y| ≧ blocked.length,則代表可以從起點「逃出」所有潛在有被阻礙住的部分(記得不要重複走已經(jīng)走過的格子,基本上跟一般的 DFS 和 BFS 一致);
又或者是我們確實可以直接抵達對方(source 到 target 或 target 到 source)。

至於為何判斷 |X - x| + |Y - y| ≧ blocked.length 就可以知道接下來不會被限制住?

因為可以看到如果我們要用 blocked.length 個格子來把 source(或是 target,這邊以 source 為例)困在一個盡可能大的區(qū)域,則最佳策略會是用一條由若干個格子組成對角線把 source 擋在角落或是直接把 source 圍一圈框起來。

兩者的「牆壁」最多就是離 source 有 blocked.length 步這麼遠(實際上不會到剛好這個大,但比較方便理解),因此一旦我們抵達 (x, y) 這種位置,就代表 source 周遭沒有牆壁(但不代表 target 那邊沒有,所以它也要做一次判斷)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創(chuàng)作回應(yīng)

更多創(chuàng)作