難度: 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
記憶體用最少的那個解答滿酷的。