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

[Swift]LeetCode749.隔离病毒|ContainVirus

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region -- the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used. 

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained. 

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells. 

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls. 

Note:

  1. The number of rows and columns of gridwill each be in the range [1, 50].
  2. Each grid[i][j] will be either 0 or 1.
  3. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

病毒扩散得很快,现在你的任务是尽可能地通过安装防火墙来隔离病毒。

假设世界由二维矩阵组成,0 表示该区域未感染病毒,而 1 表示该区域已感染病毒。可以在任意 2 个四方向相邻单元之间的共享边界上安装一个防火墙(并且只有一个防火墙)。

每天晚上,病毒会从被感染区域向相邻未感染区域扩散,除非被防火墙隔离。现由于资源有限,每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域(一个区域或连续的一片区域),且该感染区域对未感染区域的威胁最大且保证唯一。

你需要努力使得最后有部分区域不被病毒感染,如果可以成功,那么返回需要使用的防火墙个数; 如果无法实现,则返回在世界被病毒全部感染时已安装的防火墙个数。 

示例 1:

输入: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
输出: 10
说明:
一共有两块被病毒感染的区域: 从左往右第一块需要 5 个防火墙,同时若该区域不隔离,晚上将感染 5 个未感染区域(即被威胁的未感染区域个数为 5);
第二块需要 4 个防火墙,同理被威胁的未感染区域个数是 4。因此,第一天先隔离左边的感染区域,经过一晚后,病毒传播后世界如下:
[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]
第二题,只剩下一块未隔离的被感染的连续区域,此时需要安装 5 个防火墙,且安装完毕后病毒隔离任务完成。

示例 2:

输入: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
输出: 4
说明: 
此时只需要安装 4 面防火墙,就有一小区域可以幸存,不被病毒感染。
注意不需要在世界边界建立防火墙。 

示例 3:

输入: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
输出: 13
说明: 
在隔离右边感染区域后,隔离左边病毒区域只需要 2 个防火墙了。 

说明:

  1. grid 的行数和列数范围是 [1, 50]。
  2.  grid[i][j] 只包含 0 或 1 。
  3. 题目保证每次选取感染区域进行隔离时,一定存在唯一一个对未感染区域的威胁最大的区域。

Runtime: 92 ms
Memory Usage: 19.5 MB
 1 class Solution {
 2     func containVirus(_ grid: [[Int]]) -> Int {
 3         var grid = grid
 4         var res:Int = 0
 5         var m:Int = grid.count
 6         var n:Int = grid[0].count
 7         var dirs:[[Int]] = [[-1,0],[0,1],[1,0],[0,-1]]
 8         while (true )
 9         {
10             var visited:Set<Int> = Set<Int>()
11             var all:[[[Int]]] = [[[Int]]]()
12             for i in 0..<m
13             {
14                 for j in 0..<n
15                 {
16                     if grid[i][j] == 1 && !visited.contains(i * n + j)
17                     {
18                         var q:[Int] = [i * n + j]
19                         var virus:[Int] = [i * n + j]
20                         var walls:[Int] = [Int]()
21                         visited.insert(i * n + j)
22                         while(!q.isEmpty)
23                         {
24                             var t:Int = q.removeFirst()                            
25                             for dir in dirs
26                             {
27                                 var x:Int = (t / n) + dir[0]
28                                 var y:Int = (t % n) + dir[1]
29                                 if x < 0 || x >= m || y < 0 || y >= n || visited.contains(x * n + y)
30                                 {
31                                     continue
32                                 }
33                                 if grid[x][y] == -1
34                                 {
35                                     continue
36                                 }
37                                 else if grid[x][y] == 0
38                                 {
39                                     walls.append(x * n + y)
40                                 }
41                                 else if grid[x][y] == 1
42                                 {
43                                     visited.insert(x * n + y)
44                                     virus.append(x * n + y)
45                                     q.append(x * n + y)
46                                 }
47                             }                            
48                         }   
49                         var s:Set<Int> = Set(walls)
50                         var cells:[Int] = [s.count]
51                         all.append([cells ,walls, virus])
52                     }
53                 }
54             }
55             if all.isEmpty {break}
56             all.sort(by:{(a:[[Int]],b:[[Int]]) -> Bool in 
57                         return a[0][0] > b[0][0]})
58             for i in 0..<all.count
59             {
60                 if i == 0
61                 {
62                     var virus:[Int] = all[0][2]
63                     for idx in virus
64                     {
65                         grid[idx / n][idx % n] = -1
66                     }
67                     res += all[0][1].count
68                 }
69                 else
70                 {
71                     var wall:[Int] = all[i][1]
72                     for idx in wall
73                     {
74                         grid[idx / n][idx % n] = 1
75                     }
76                 }
77             }     
78         }
79         return res
80     }
81 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift-5-流程控制发布时间:2022-07-13
下一篇:
Swift面试题发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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