Leetcode題解 Python：Check if There is a Valid Path in a Grid

給一個二維串列 grid，每格代表一種道路，其值可以對應下表，要回傳是否能從左上角走到右下角。

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

對於這種地圖或是面積的圖像問題，我總是感到棘手，也許有一套通用思路，不過可能需要很多經驗值累積才能解得順手。

從左上角開始，但是沒有規定左上角一定是從外面延伸進來，如果是 grid[0][0]  == 5，一開始就死局。如果等於 4，那一開始就會有兩條路線。

要怎麼解決起始有兩條路線的問題，就會是一個難題。又或者拋開心中虛擬的小車車，直接用遞迴 + memo 去從(0, 0)拔起所有合格座標，再看看右下角是否存在。

街道有六種形式，而且具有方向問題，困難點在此，要怎麼妥善解決轉向，這就值得思考。


每一種街道只能接受兩種方向，例如 street 1，如果從右邊來，通過後方向朝左邊；如果從左邊來，通過後方向朝右邊。如果從其他方向，那就代表無法接到一起。

街道對應的方向就只能老實打出，無法再快，這是題目的定義。

如果在當前位置向右走，對下一個位置是從左來，對於制定方向前進的人，要留意方向上的切換。

思考一下之後，使用遞迴拔出所有與(0,0)連接的街道會比較泛用。

class Solution:
    def hasValidPath(self, grid):
        """
        1 which means a street connecting the left cell and the right cell.
        2 which means a street connecting the upper cell and the lower cell.
        3 which means a street connecting the left cell and the lower cell.
        4 which means a street connecting the right cell and the lower cell.
        5 which means a street connecting the left cell and the upper cell.
        6 which means a street connecting the right cell and the upper cell.
        """   
        # 0 up 1 left 2 down 3 right        
        streets = {1:(1,3), 2:(0,2), 3:(1,2), 4:(3,2), 5:(1,0), 6:(3,0)}

        path = set()
        rows, cols = len(grid), len(grid[0]) 

        def searchMap(y,x):
            if y < 0 or x < 0: return 
            if y == rows or x == cols: return
            path.add((y,x))
            ds = streets[grid[y][x]]
   
            for d in ds:
                x2,y2=x,y
                if d == 0:                    
                    y2 = y-1
                elif d == 1:
                    x2 = x-1
                elif d == 2:
                    y2 = y+1
                else:
                    x2 = x+1
                d = (d+2)%4 #換方向(下一個位置的相對方向)
                if (y2, x2) not in path:
                    if y2 < 0 or x2 < 0 or y2 == rows or x2 == cols: 
                        continue
                    elif d in streets[grid[y2][x2]]:
                        searchMap(y2,x2)

        searchMap(0,0)
        return (rows-1, cols-1 ) in path