[Swift]LeetCode959.由斜杠划分区域|RegionsCutBySlashes

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

Example 4:

Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

Example 5:

Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。

返回区域的数目。

示例 1：

输入：
[
  " /",
  "/ "
]
输出：2
解释：2x2 网格如下：

示例 2：

输入：
[
  " /",
  "  "
]
输出：1
解释：2x2 网格如下：

示例 3：

输入：
[
  "\\/",
  "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：

示例 4：

输入：
[
  "/\\",
  "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：

示例 5：

输入：
[
  "//",
  "/ "
]
输出：3
解释：2x2 网格如下：

提示：

1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。

104ms

 1 class Solution {
 2     let TOP = 0, LEFT = 1, RIGHT = 2, BOTTOM = 3
 3     
 4     func regionsBySlashes(_ grid: [String]) -> Int {
 5         var len:Int = grid.count
 6         //定义三维数组，元素初始化为0，由内往外
 7         var g = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: 4), count: len), count: len)
 8         var n:Int = 0
 9         for i in 0..<len
10         {
11             for j in 0..<len
12             {
13                 for k in 0..<4
14                 {
15                     if g[i][j][k] == 0
16                     {
17                         n += 1
18                         mark(grid, &g, i, j, k, n) 
19                     }
20                 }
21             }
22         }
23         return n
24     }
25     
26     func mark(_ grid:[String],_ g: inout [[[Int]]],_ i:Int,_ j:Int,_ k:Int,_ n: Int)
27     {
28         var len:Int = g.count
29         if i < 0 || i >= len || j < 0 || j >= len || g[i][j][k] != 0 {return}
30         g[i][j][k] = n
31         var c:Character = grid[i][j]
32         if c == "/"
33         {
34             if k == LEFT || k == TOP
35             {
36                 mark(grid, &g, i, j, LEFT, n)
37                 mark(grid, &g, i, j, TOP, n)
38             }
39             else
40             {
41                 mark(grid, &g, i, j, BOTTOM, n)
42                 mark(grid, &g, i, j, RIGHT, n)
43             }
44         }
45         else if c == "\\"
46         {
47             if k == LEFT || k == BOTTOM
48             {
49                 mark(grid, &g, i, j, LEFT, n)
50                 mark(grid, &g, i, j, BOTTOM, n)
51             }
52             else
53             {
54                 mark(grid, &g, i, j, TOP, n)
55                 mark(grid, &g, i, j, RIGHT, n)
56             }
57         }
58         else
59         {
60             mark(grid, &g, i, j, TOP, n)
61             mark(grid, &g, i, j, LEFT, n)
62             mark(grid, &g, i, j, RIGHT, n)
63             mark(grid, &g, i, j, BOTTOM, n)
64         }
65         
66         if k == LEFT
67         {
68             mark(grid, &g, i, j - 1, RIGHT, n)
69         }
70         else if k == RIGHT
71         {
72             mark(grid, &g, i, j + 1, LEFT, n)
73         }
74         else if k == BOTTOM
75         {
76            mark(grid, &g, i + 1, j, TOP, n)
77         }
78         else if k == TOP
79         {
80             mark(grid, &g, i - 1, j, BOTTOM, n)
81         }
82     }
83 }
84 
85 extension String {        
86     //subscript函数可以检索数组中的值
87     //直接按照索引方式截取指定索引的字符
88     subscript (_ i: Int) -> Character {
89         //读取字符
90         get {return self[index(startIndex, offsetBy: i)]}
91     }
92 }

180ms

 1 class Solution {
 2     func regionsBySlashes(_ grid: [String]) -> Int {
 3         let N = grid.count
 4         let dsu = DSU(4 * N * N)
 5         for r in 0..<N {
 6             for c in 0..<N {
 7                 let root = 4 * (r * N + c)
 8                 let val = Array(grid[r])[c]
 9                 if val != "\\" {
10                     dsu.union(root, root + 1)
11                     dsu.union(root + 2, root + 3)
12                 }
13                 if val != "/" {
14                     dsu.union(root, root + 2)
15                     dsu.union(root + 1, root + 3)
16                 }
17                 if r + 1 < N {
18                     dsu.union(root + 3, root + 4 * N)
19                 }
20                 if r - 1 >= 0 {
21                     dsu.union(root, root - 4 * N + 3)
22                 }
23                 if c + 1 < N {
24                     dsu.union(root + 2, root + 4 + 1)
25                 }
26                 if c - 1 >= 0 {
27                     dsu.union(root + 1, root - 4 + 2)
28                 }
29             }
30         }
31         var ans = 0
32         for x in 0..<4 * N * N where dsu.find(x) == x { ans += 1 }
33         return ans
34     }
35 }
36 
37 class DSU {
38     var parent: [Int]
39     init(_ N: Int) {
40         parent = Array(repeating: 0, count: N)
41         for i in 0..<N { parent[i] = i }
42     }
43     func find(_ x: Int) -> Int {
44         if parent[x] != x { parent[x] = find(parent[x]) }
45         return parent[x]
46     }
47     func union(_ x: Int, _ y: Int) {
48         parent[find(x)] = find(y)
49     }
50 }

200ms

 1 class Solution {
 2     let convertDict: [Character: [[Int]]] = [
 3         "/": [[0,0,1], [0,1,0], [1,0,0]],
 4         "\\": [[1,0,0], [0,1,0], [0,0,1]]
 5     ]
 6     
 7     func regionsBySlashes(_ grid: [String]) -> Int {
 8         // convert
 9         var map = [[Int]]()
10         for row in grid {
11             var line0 = [Int](), line1 = [Int](), line2 = [Int]()
12             for (idx, char) in row.enumerated() {
13                 let converted = convertDict[char] ?? [[0,0,0],[0,0,0],[0,0,0]]
14                 line0 += converted[0]
15                 line1 += converted[1]
16                 line2 += converted[2]
17             }
18             map += [line0, line1, line2]
19         }
20         
21         // perform
22         var result = 0
23         for i in 0..<map.count {
24             for j in 0..<map[i].count {
25                 if map[i][j] == 0 {
26                     result += 1
27                     dfs(i, j, &map)
28                 }
29             }
30         }
31         return result
32     }
33     
34     func dfs(_ i: Int, _ j: Int, _ map: inout [[Int]]) {
35         guard i >= 0 && i < map.count else { return }
36         let row = map[i]
37         guard j >= 0 && j < row.count else { return }
38         guard map[i][j] == 0 else { return }
39         map[i][j] = -1
40         dfs(i-1, j, &map)
41         dfs(i+1, j, &map)
42         dfs(i, j-1, &map)
43         dfs(i, j+1, &map)
44     }
45 }