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,2,-1]]Output: 2 Explanation: We have the following two paths: 1. (0,0),(0,1),2),3),(1,(2,2) 2. (0,2)
Example 2:
input: [[1,2]]Output: 4 Explanation: We have the following four paths: 1. (0,3) 2. (0,3) 3. (0,3) 4. (0,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
在二维网格 grID
上,有 4 种类型的方格:
1
表示起始方格。且只有一个起始方格。 2
表示结束方格,且只有一个结束方格。 0
表示我们可以走过的空方格。 -1
表示我们无法跨越的障碍。 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目,每一个无障碍方格都要通过一次。
示例 1:
输入:[[1,-1]]输出:2解释:我们有以下两条路径:1. (0,2)2. (0,2)
示例 2:
输入:[[1,2]]输出:4解释:我们有以下四条路径: 1. (0,3)2. (0,3)3. (0,3)4. (0,3)
示例 3:
输入:[[0,0]]输出:0解释:没有一条路能完全穿过每一个空的方格一次。请注意,起始和结束方格可以位于网格中的任意位置。
提示:
1 <= grID.length * grID[0].length <= 20
32ms
1 class Solution { 2 var zero:Int = 0 3 var ans:Int = 0 4 func uniquePathsIII(_ grID: [[Int]]) -> Int { 5 var start1:Int = 0 6 var start2:Int = 0 7 for i in 0..<grID.count 8 { 9 for j in 0..<grID[0].count10 {11 if grID[i][j] == 012 {13 zero += 114 }15 if grID[i][j] == 116 {17 start1 = i18 start2 = j19 }20 } 21 }22 var visited:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:grID[0].count),count:grID.count)23 dfs(grID,start1,start2,visited,0)24 return ans25 }26 27 func dfs(_ grID: [[Int]],_ i:Int,_ j:Int,_ visited: [[Int]],_ count:Int)28 {29 var visited = visited30 if i < 0 || i >= grID.count || j < 0 || j >= grID[0].count || visited[i][j] == 1 || grID[i][j] == -131 {32 return33 }34 if grID[i][j] == 235 {36 if count == zero + 137 {38 ans += 139 }40 return41 }42 visited[i][j] = 143 dfs(grID,i+1,j,count+1)44 dfs(grID,i-1,count+1)45 dfs(grID,i,j-1,count+1)46 dfs(grID,j+1,count+1)47 visited[i][j] = 048 }49 }总结
以上是内存溢出为你收集整理的[Swift Weekly Contest 120]LeetCode980. 不同路径 III | Unique Paths III全部内容,希望文章能够帮你解决[Swift Weekly Contest 120]LeetCode980. 不同路径 III | Unique Paths III所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)