[Swift]LeetCode827.最大人工岛|MakingALargeIsland

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

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

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

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

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

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

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

示例 1:

输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

说明:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 1

Runtime: 104 ms

Memory Usage: 19.9 MB

 1 class Solution {
 2     var N:Int = 0
 3     func largestIsland(_ grid: [[Int]]) -> Int {
 4         var grid = grid
 5         N = grid.count
 6         var index:Int = 3
 7         var res:Int = 0
 8         var area:[Int:Int] = [Int:Int]()
 9         for x in 0..<N
10         {
11             for y in 0..<N
12             {
13                 if grid[x][y] == 1
14                 {
15                     area[index] = dfs(&grid, x, y, index)
16                     res = max(res, area[index,default:0])
17                     index += 1
18                 }
19             }
20         }
21         for x in 0..<N
22         {
23             for y in 0..<N
24             {
25                 if grid[x][y] == 0
26                 {
27                     var seen:Set<Int> = Set<Int>()
28                     var cur:Int = 1
29                     for (key,val) in move(x, y)
30                     {
31                         index = grid[key][val]
32                         if index > 1 && !seen.contains(index)
33                         {
34                             seen.insert(index)
35                             cur += area[index,default:0]
36                         }
37                     }
38                     res = max(res, cur)
39                 }
40             }
41         }
42         return res
43     }
44     
45     func move(_ x:Int,_ y:Int) -> [(Int,Int)]
46     {
47         var res:[(Int,Int)] = [(Int,Int)]()
48         if valid(x, y + 1) {res.append((x, y + 1))}
49         if valid(x, y - 1) {res.append((x, y - 1))}
50         if valid(x + 1, y) {res.append((x + 1, y))}
51         if valid(x - 1, y) {res.append((x - 1, y))}
52         return res        
53     }
54     
55     func valid(_ x:Int,_ y:Int) -> Bool
56     {
57         return 0 <= x && x < N && 0 <= y && y < N
58     }
59     
60     func dfs(_ grid:inout [[Int]],_ x:Int,_ y:Int,_ index:Int) -> Int
61     {
62         var area:Int = 0
63         grid[x][y] = index
64         for (key,val) in move(x, y)
65         {
66             if grid[key][val] == 1
67             {
68                 area += dfs(&grid, key, val, index) 
69             }
70         }
71         return area + 1
72     }
73 }