[Swift]LeetCode1034.边框着色|ColoringABorder

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

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

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

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

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

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

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

Example 1:

Input: grid = 3
Output: [[3, 3], [3, 2]]

Example 2:

Input: grid = 3
Output: [[1, 3, 3], [2, 3, 3]]

Example 3:

Input: grid = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]

Note:

1 <= grid.length <= 50
1 <= grid[0].length <= 50
1 <= grid[i][j] <= 1000
0 <= r0 < grid.length
0 <= c0 < grid[0].length
1 <= color <= 1000

给出一个二维整数网格 grid，网格中的每个值表示该位置处的网格块的颜色。

只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。

连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。

给出位于 (r0, c0) 的网格块和颜色 color，使用指定颜色 color 为所给网格块的连通分量的边界进行着色，并返回最终的网格 grid 。

示例 1：

输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
输出：[[3, 3], [3, 2]]

示例 2：

输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
输出：[[1, 3, 3], [2, 3, 3]]

示例 3：

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]

提示：

1 <= grid.length <= 50
1 <= grid[0].length <= 50
1 <= grid[i][j] <= 1000
0 <= r0 < grid.length
0 <= c0 < grid[0].length
1 <= color <= 1000

140ms

 1 class Solution {
 2     func colorBorder(_ grid: [[Int]], _ r0: Int, _ c0: Int, _ color: Int) -> [[Int]] {
 3         guard !grid.isEmpty else { return grid }
 4         guard !grid[0].isEmpty else { return grid }
 5         guard grid[r0][c0] != color else { return grid }
 6         
 7         let h = grid.count
 8         let w = grid[0].count
 9         
10         var result = grid
11         var queue = [(r0, c0)]
12         var visited = Set<Int>()
13         
14         while !queue.isEmpty {
15             var nextQueue = [(Int, Int)]()
16             for (r, c) in queue {
17                 let key = r * w + c
18                 guard !visited.contains(key) else { continue }
19                 visited.insert(r * w + c)
20                 
21                 if r == 0 || c == 0 || r == h - 1 || c == w - 1 {
22                     result[r][c] = color
23                 }
24                 
25                 let this = grid[r][c]
26                 var validNeighbors = [(Int, Int)]()
27                 
28                 if r > 0 {
29                     validNeighbors.append((r - 1, c))
30                 }
31                 
32                 if r < h - 1 {
33                     validNeighbors.append((r + 1, c))
34                 }
35                 
36                 if c > 0 {
37                     validNeighbors.append((r, c - 1))
38                 }
39                 
40                 if c < w - 1 {
41                     validNeighbors.append((r, c + 1))
42                 }
43                 
44                 for neighbor in validNeighbors {
45                     if grid[neighbor.0][neighbor.1] != this {
46                         result[r][c] = color
47                     } else if !visited.contains(neighbor.0 * w + neighbor.1) {
48                         nextQueue.append((neighbor.0, neighbor.1))
49                     }
50                 }
51             }
52             queue = nextQueue
53         }
54         
55         return result
56     }
57 }

144ms

 1 class Solution {
 2             
 3     func dfs(_ grid: inout [[Int]], _ r: Int, _ c: Int, _ color: Int)  {
 4         if r < 0 || c < 0 || r >= grid.count || c >= grid[r].count || grid[r][c] != color {
 5             return
 6         }
 7         grid[r][c] = -color
 8         let directs = [(1,0), (-1, 0), (0, 1), (0, -1)]
 9         for direct in directs {
10             dfs(&grid, r + direct.0, c + direct.1, color)
11         }
12 
13         if r > 0 && r < grid.count - 1 && c > 0 && c < grid[r].count - 1 && (directs.filter { color != abs(grid[r + $0.0][$0.1 + c]) }.count == 0) {
14             grid[r][c] = color
15         }
16     }
17 
18     func colorBorder(_ grid: [[Int]], _ r0: Int, _ c0: Int, _ color: Int) -> [[Int]] {
19         var grid = grid
20         dfs(&grid, r0, c0, grid[r0][c0]);
21         for i in grid.indices {
22             for j in grid[0].indices {
23                 grid[i][j] = grid[i][j] < 0 ? color : grid[i][j]
24             }
25         }
26         return grid
27     }
28 }

160ms

 1 class Solution {
 2     func colorBorder(_ grid: [[Int]], _ r0: Int, _ c0: Int, _ color: Int) -> [[Int]] {
 3         guard !grid.isEmpty else { return grid }
 4         guard !grid[0].isEmpty else { return grid }
 5         guard grid[r0][c0] != color else { return grid }
 6         
 7         let h = grid.count
 8         let w = grid[0].count
 9         
10         var result = grid
11         var queue = [(r0, c0)]
12         var visited = Set<Int>()
13         
14         while !queue.isEmpty {
15             var nextQueue = [(Int, Int)]()
16             for (r, c) in queue {
17                 let key = r * w + c
18                 guard !visited.contains(key) else { continue }
19                 visited.insert(r * w + c)
20                 
21                 if r == 0 || c == 0 || r == h - 1 || c == w - 1 {
22                     result[r][c] = color
23                 }
24                 
25                 let this = grid[r][c]
26                 var validNeighbors = [(Int, Int)]()
27                 
28                 if r > 0 {
29                     validNeighbors.append((r - 1, c))
30                 }
31                 
32                 if r < h - 1 {
33                     validNeighbors.append((r + 1, c))
34                 }
35                 
36                 if c > 0 {
37                     validNeighbors.append((r, c - 1))
38                 }
39                 
40                 if c < w - 1 {
41                     validNeighbors.append((r, c + 1))
42                 }
43                 
44                 for neighbor in validNeighbors {
45                     if grid[neighbor.0][neighbor.1] != this {
46                         result[r][c] = color
47                     } else if !visited.contains(neighbor.0 * w + neighbor.1) {
48                         nextQueue.append((neighbor.0, neighbor.1))
49                     }
50                 }
51             }
52             queue = nextQueue
53         }
54         
55         return result
56     }
57 }

Runtime: 160 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     var conn:[[Int]] = [[Int]]()
 3     var col:[[Int]] = [[Int]]()
 4     var H:Int = 0
 5     var W:Int = 0
 6     var dx:[Int] = [1, -1, 0, 0]
 7     var dy:[Int] = [0, 0, 1, -1]
 8     
 9     func colorBorder(_ grid: [[Int]], _ r0: Int, _ c0: Int, _ color: Int) -> [[Int]] {
10         H = grid.count
11         W = grid[0].count
12         conn = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)
13         col = grid
14         dfs_con(r0, c0)
15         var ret:[[Int]] = grid
16         for x in 0..<H
17         {
18             for y in 0..<W
19             {
20                 if conn[x][y] != 0
21                 {
22                     for d in 0..<4
23                     {
24                         let xn:Int = x + dx[d]
25                         let yn:Int = y + dy[d]
26                         if xn < 0 || yn < 0 || xn >= H || yn >= W || grid[xn][yn] != grid[r0][c0]
27                         {
28                             ret[x][y] = color
29                         }
30                     }
31                 }
32             }
33         }
34         return ret
35     }
36     
37     func dfs_con(_ x:Int,_ y:Int)
38     {
39         conn[x][y] = 1
40         for d in 0..<4
41         {
42             let xn:Int = x + dx[d]
43             let yn:Int = y + dy[d]
44             if xn < 0 || yn < 0 || xn >= H || yn >= W
45             {
46                 continue
47             }
48             if col[x][y] == col[xn][yn] && conn[xn][yn] == 0
49             {
50                 dfs_con(xn, yn)
51             }
52         }
53     }
54 }