[Swift Weekly Contest 120]LeetCode980. 不同路径 III | Unique
发布时间:2020-12-14 05:05:39 所属栏目:百科 来源:网络整理
导读: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
On a 2-dimensional?
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: 输入:[[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 解释: 没有一条路能完全穿过每一个空的方格一次。 请注意,起始和结束方格可以位于网格中的任意位置。? 提示:
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].count 10 { 11 if grid[i][j] == 0 12 { 13 zero += 1 14 } 15 if grid[i][j] == 1 16 { 17 start1 = i 18 start2 = j 19 } 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 ans 25 } 26 27 func dfs(_ grid: [[Int]],_ i:Int,_ j:Int,_ visited: [[Int]],_ count:Int) 28 { 29 var visited = visited 30 if i < 0 || i >= grid.count || j < 0 || j >= grid[0].count || visited[i][j] == 1 || grid[i][j] == -1 31 { 32 return 33 } 34 if grid[i][j] == 2 35 { 36 if count == zero + 1 37 { 38 ans += 1 39 } 40 return 41 } 42 visited[i][j] = 1 43 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] = 0 48 } 49 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |