題目
在二維網格 grid 上，有 4 種類型的方格：
1 表示起始方格。且只有一個起始方格。
2 表示結束方格，且只有一個結束方格。
0 表示我們可以走過的空方格。
-1 表示我們無法跨越的障礙。
返回在四個方向（上、下、左、右）上行走時，從起始方格到結束方格的不同路徑的數目。
每一個無障礙方格都要透過一次，但是一條路徑中不能重複透過同一個方格。
示例 1：輸入：［［1，0，0，0］，［0，0，0，0］，［0，0，2，-1］］ 輸出：2
解釋：我們有以下兩條路徑：
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）
示例 2：輸入：［［1，0，0，0］，［0，0，0，0］，［0，0，0，2］］ 輸出：4
解釋：我們有以下四條路徑：
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）
示例 3：輸入：［［0，1］，［2，0］］ 輸出：0
解釋：沒有一條路能完全穿過每一個空的方格一次。
請注意，起始和結束方格可以位於網格中的任意位置。
提示：1 <= grid。length * grid［0］。length <= 20
解題思路分析
1、回溯；時間複雜度
O（4^（n*n））
，空間複雜度
O（n^2）
var res intvar n， m intfunc uniquePathsIII（grid ［］［］int） int { res = 0 n， m = len（grid）， len（grid［0］） visited ：= make（［］［］bool， n） for i ：= 0； i < n； i++ { visited［i］ = make（［］bool， m） } x， y ：= 0， 0 count ：= 0 for i ：= 0； i < n； i++ { for j ：= 0； j < m； j++ { if grid［i］［j］ == 1 { x， y = i， j continue } if grid［i］［j］ == 0 { count++ } } } dfs（grid， x， y， visited， count） return res}func dfs（grid ［］［］int， i， j int， visited ［］［］bool， count int） { if i < 0 || i >= n || j < 0 || j >= m || grid［i］［j］ == -1 || visited［i］［j］ == true { return } if grid［i］［j］ == 2 { if count == -1 { // 包括起始點1 res++ } return } visited［i］［j］ = true dfs（grid， i， j+1， visited， count-1） dfs（grid， i， j-1， visited， count-1） dfs（grid， i+1， j， visited， count-1） dfs（grid， i-1， j， visited， count-1） visited［i］［j］ = false}
總結
Hard題目，使用回溯嘗試所有的可能
