有一個 n * n 大小的網格，有一條蛇佔據二格，要從 (0,0) 和 (0,1) 移動到 (n-1,n-2) 和 (n-1, n-1)。
網格上的點為 0 代表是空的， 1 代表障礙。
蛇可以往右移或往下移，或是旋轉，旋轉以左上方的那格為基準，轉朝下或右。旋轉時鄰近右下那一格必需是 0 。
這題光寫基本流程就蠻花時間的，其實並不難。
首先如果有二個點且中間有障礙，要找最短路徑。可以想像用一個越來越大的圓，圓心是出發點，最後圓納入終點的時候，其半徑即為最短路徑。
向外擴張的時候，可以把每輪向外的一步都當成新的圓半徑。為了要實現這樣的方式，不能使用 DFS ，要用像是二元樹的階層式往深探索。
起點(0,0) steps: 0，下一輪往四周 (-1,0), (0,1), (0,-1), (1,0) steps: 1，為了避免重複尋找，要把找過的位置加入 memo ，
若從 memo 找到要找的位置，就直接換下一個找。
這題蛇加入了「旋轉」，朝右或朝下會影響下一步能怎麼走，所以除了位置之外，保存狀態也是必要的。
每一步以 (row, col, state) 保存，並且在每次尋找最前方做判斷，為中止條件。
如果以一個起點出發，要是可以通，在找到路徑之前，就會先探索許多背離終點的路徑。更好的作法是再加上從終點尋找，只要二者路徑重疊到，就代表找到最短路徑。
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
# (row, col, state) = steps。 state: right = 0, down = 1.
n = len(grid)
path = set()
steps = [(0,0,0)]
ans = 0
while steps:
for _ in range(len(steps)):
row, col, state = steps.pop(0)
if (row, col, state) in path: continue
if row == n-1 and col == n-2 : return ans
path.add((row, col, state))
shortPath = []
if state == 0:
if col+2 < n and grid[row][col+2] == 0:
steps.append((row, col+1, state))
if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
steps.append((row+1, col, state))
steps.append((row, col, 1))
else:
if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
steps.append((row, col+1, state))
steps.append((row, col, 0))
if row+2 < n and grid[row+2][col] == 0 :
steps.append((row+1, col, state))
ans += 1
return -1
Python(Two Start Point)
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
# (row, col, state) = steps。 state: right = 0, down = 1.
n = len(grid)
path = set()
path2 = set()
steps = [(0,0,0)]
steps2 = [(n-1,n-2,0)]
ans = -1
while steps and steps2:
for _ in range(len(steps)):
row, col, state = steps.pop(0)
if (row, col, state) in path: continue
if (row, col, state) in path2: return ans
path.add((row, col, state))
if state == 0:
if col+2 < n and grid[row][col+2] == 0:
steps.append((row, col+1, state))
if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
steps.append((row+1, col, state))
steps.append((row, col, 1))
else:
if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
steps.append((row, col+1, state))
steps.append((row, col, 0))
if row+2 < n and grid[row+2][col] == 0 :
steps.append((row+1, col, state))
ans += 1
for _ in range(len(steps2)):
row, col, state = steps2.pop(0)
if (row, col, state) in path2: continue
if (row, col, state) in path: return ans
path2.add((row, col, state))
if state == 0:
if col-1 >= 0 and grid[row][col-1] == 0:
steps2.append((row, col-1, state))
if row-1 >= 0 and grid[row-1][col] == 0 and grid[row-1][col+1] == 0:
steps2.append((row-1, col, state))
if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
steps2.append((row, col, 1))
else:
if row-1 >= 0 and grid[row-1][col] == 0 :
steps2.append((row-1, col, state))
if col-1 >= 0 and grid[row][col-1] == 0 and grid[row+1][col-1] == 0:
steps2.append((row, col-1, state))
if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
steps2.append((row, col, 0))
ans += 1
return -1
## 非正解，不小心寫錯的版本
Python(可上下左右的版本)
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
# dp[row][col][state] = steps
# state: right = 0, down = 1.
# return dp[row-1][col-2][0]
n = len(grid)
path = set()
steps = [(0,0,0)]
ans = 0
while steps:
for _ in range(len(steps)):
row, col, state = steps.pop(0)
if (row, col, state) in path: continue
if row == n-1 and col == n-2 : return ans
path.add((row, col, state))
if state == 0:
if 0 and col-1 >= 0 and grid[row][col-1] == 0:
steps.append((row, col-1, state))
if col+2 < n and grid[row][col+2] == 0:
steps.append((row, col+1, state))
if 0 and row-1 >= 0 and grid[row-1][col] == 0 and grid[row-1][col+1] == 0:
steps.append((row-1, col, state))
if row+1 < n and grid[row+1][col] == 0 and grid[row+1][col+1] == 0:
steps.append((row+1, col, state))
steps.append((row, col, 1))
else:
if 0 and col-1 >= 0 and grid[row][col-1] == 0 and grid[row+1][col-1] == 0:
steps.append((row, col-1, state))
if col+1 < n and grid[row][col+1] == 0 and grid[row+1][col+1] == 0:
steps.append((row, col+1, state))
steps.append((row, col, 0))
if 0 and row-1 >= 0 and grid[row-1][col] == 0 :
steps.append((row-1, col, state))
if row+2 < n and grid[row+2][col] == 0 :
steps.append((row+1, col, state))
ans += 1
return -1