前往
大廳
主題

[leetcode]1210. Minimum Moves to Reach Target with Rotations

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-20 12:00:05 | 巴幣 4 | 人氣 241

題目: 1210. Minimum Moves to Reach Target with Rotations
難度: Hard
目前下列解法的時間複雜度: O(n*n)


題目說明

給定一個值只有 0 或 1 的 n*n 方格, 0 代表此處是空的; 1 代表此處為障礙物。
現在有一條 2*1 的蛇位在左上角,佔據 (0, 0) 和 (0, 1) ,此蛇的目標是要走到佔據 (n-1, n-2) 和 (n-1, n-1) 的位置。
(題目給的座標方式應理解為 (row,column) 或 (y,x) 而非 (x,y) )
此蛇每 1 步有下列動作可以做:
a. 往右走,如果走完後蛇身都沒碰到障礙物
b. 往下走,如果走完後蛇身都沒碰到障礙物
c. 當蛇是水平方向時,且下方格子皆為空的,則可往順時針方向轉90度
d. 當蛇是鉛直方向時,且右方格子皆為空的,則可往逆時針方向轉90度
求此蛇達成目標的最小步數。


解法: BFS

1. BFS 。每步成本相等,用 queue 即可。
2. 狀態數最多 n*n*2 ;每個狀態固定延伸出最多另外 4 個狀態,故時間複雜度為 O(n*n*4) = O(n*n)


source code

記憶體用最少的那個解答滿酷的。

創作回應

相關創作

更多創作