# 980. Unique Paths III (hard)
###### tags: `online_judge`, `python3`

地圖尋路題，從```1```走到```2```，過程必須把所有的```0```都走過有且只有 1 次。

單純的 DFS 尋路即可解開。在開始尋路前記錄```0```的數量。在遞迴過程中以遞迴深度作為是否走過所有```0```的判斷。注意離開該次遞迴時必須把走過該點的標記恢復（本題走過即標記為```-1```）。

小技巧：
地圖題很多時候可以在邊緣圍上一層不可進入的標記，以省去處理邊緣問題的時間。

例如：

1  0  0
0 -1  0
0  0  2

可修改為：

-1 -1 -1 -1 -1
-1  1  0  0 -1
-1  0 -1  0 -1
-1  0  0  2 -1
-1 -1 -1 -1 -1

這樣就可以在整個尋路過程中使用同一套邏輯了。

---

### 題目

On a 2-dimensional grid, there are 4 types of squares:

    1 represents the starting square.  There is exactly one starting square.
    2 represents the ending square.  There is exactly one ending square.
    0 represents empty squares we can walk over.
    -1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

 

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

 

Note:

    1 <= grid.length * grid[0].length <= 20

---

### 解答

class Solution:
    
    zero_count = 0
    max_x = 0
    max_y = 0
    path_count = 0
    
    def get_info(self, grid):
        s_x = -1
        s_y = -1
        zero_count = 0
        
        for i in range(self.max_y):
            for j in range(self.max_x):
                if grid[i][j] == 0:
                    zero_count += 1
                elif grid[i][j] == 1:
                    s_x = j
                    s_y = i
        return s_x,s_y,zero_count
        
    def find_path(self, grid, x, y, count):
        
        grid[y][x] = -1
        
        if grid[y][x+1] == 0:
            self.find_path(grid,x+1,y,count+1)
        elif grid[y][x+1] == 2 and count == self.zero_count:
            self.path_count += 1
            
        if grid[y][x-1] == 0:
            self.find_path(grid,x-1,y,count+1)
        elif grid[y][x-1] == 2 and count == self.zero_count:
            self.path_count += 1
        
        if grid[y+1][x] == 0:
            self.find_path(grid,x,y+1,count+1)
        elif grid[y+1][x] == 2 and count == self.zero_count:
            self.path_count += 1
            
        if grid[y-1][x] == 0:
            self.find_path(grid,x,y-1,count+1)
        elif grid[y-1][x] == 2 and count == self.zero_count:
            self.path_count += 1
            
        grid[y][x] = 0
            
        return
        
    
    def uniquePathsIII(self, grid) :
        
        self.path_count = 0
        
        self.max_x = len(grid[0])
        self.max_y = len(grid)
        
        for i in range(self.max_y):
            grid[i].insert(0,-1)
            grid[i].append(-1)
        
        bound = [-1 for n in range(self.max_x + 2)]
        grid.insert(0,bound)
        grid.append(bound)
        
        self.max_x += 2
        self.max_y += 2
        
        s_x, s_y, self.zero_count = self.get_info(grid)
        
        self.find_path(grid, s_x, s_y, 0)
        return self.path_count
        
a = Solution()
a.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,2,-1]])
a.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,0,2]])
a.uniquePathsIII([[0,1],[2,0]])

---

### 成績

---