• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= grid.length == grid[0].length <= 30
  2. 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. 1 <= grid.length == grid[0].length <= 30
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap