LWC 63: 749. Contain Virus

Problem:

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 0 represents 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:

The number of rows and columns of grid will each be in the range [1, 50].

Each grid[i][j] will be either 0 or 1.

Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

思路: 此题实际上是一个模拟+贪心,首先可以简单计算每次感染后得到的边界大小。优先选择感染边界最大的,这样可以减少后续的感染人数。接下来,只需要确定每次感染后的图像,根据这些图像重新一轮计算,直到没有新的区域产生。

Java版本:

public class Solution {

    Set<Integer> vis;
    List<Set<Integer>> frontiers;
    List<Set<Integer>> regions;
    List<Integer> perimeters;
    int[][] grid;
    int n, m;

    int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    public int containVirus(int[][] grid) {
        this.grid = grid;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        while (true) {
            vis = new HashSet<>();
            frontiers = new ArrayList<>();
            regions = new ArrayList<>();
            perimeters = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (grid[i][j] ==1 && !vis.contains(i * m + j)) {
                        frontiers.add(new HashSet<>());
                        regions.add(new HashSet<>());
                        perimeters.add(0);
                        dfs(i, j);
                    }
                }
            }

            if (regions.isEmpty()) break;
            int triageIndex = 0;
            for (int i = 0; i < frontiers.size(); ++i) {
                if (frontiers.get(triageIndex).size() < frontiers.get(i).size())
                    triageIndex = i;
            }
            ans += perimeters.get(triageIndex);

            for (int i = 0; i < regions.size(); ++i) {
                if (i == triageIndex) {
                    for (int code: regions.get(i))
                        grid[code / m][code % m] = -1;
                } else {
                    for (int code: regions.get(i)) {
                        int r = code / m, c = code % m;
                        for (int[] d : dir) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0)
                                grid[nr][nc] = 1;
                        }
                    }
                }
            }
        }

        return ans;
    }

    public void dfs(int r, int c) {
        if (!vis.contains(r * m + c)) {
            vis.add(r * m + c);
            int N = regions.size();
            regions.get(N - 1).add(r * m + c);
            for (int[] d : dir) {
                int nr = d[0] + r;
                int nc = d[1] + c;
                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    if (grid[nr][nc] == 1) {
                        dfs(nr, nc);
                    }
                    else if (grid[nr][nc] == 0){
                        frontiers.get(N - 1).add(nr * m + nc);
                        perimeters.set(N - 1, perimeters.get(N - 1) + 1);
                    }
                }
            }
        }
    }

}

Python版本:

class Solution(object):
    def containVirus(self, grid):
        R, C = len(grid), len(grid[0])
        def neighbors(r, c):
            for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                if 0 <= nr < R and 0 <= nc < C:
                    yield nr, nc

        def dfs(r, c):
            if (r, c) not in seen:
                seen.add((r, c))
                regions[-1].add((r, c))
                for nr, nc in neighbors(r, c):
                    if grid[nr][nc] == 1:
                        dfs(nr, nc)
                    elif grid[nr][nc] == 0:
                        frontiers[-1].add((nr, nc))
                        perimeters[-1] += 1

        ans = 0
        while True:
            #Find all regions, with associated frontiers and perimeters.
            seen = set()
            regions = []
            frontiers = []
            perimeters = []
            for r, row in enumerate(grid):
                for c, val in enumerate(row):
                    if val == 1 and (r, c) not in seen:
                        regions.append(set())
                        frontiers.append(set())
                        perimeters.append(0)
                        dfs(r, c)

            if not regions: break

            triage_index = frontiers.index(max(frontiers, key = len))
            ans += perimeters[triage_index]

            for i, reg in enumerate(regions):
                if i == triage_index:
                    for r, c in reg:
                        grid[r][c] = -1
                else:
                    for r, c in reg:
                        for nr, nc in neighbors(r, c):
                            if grid[nr][nc] == 0:
                                grid[nr][nc] = 1

        return ans

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

HDU-1054 Strategic Game(树形DP)

Strategic Game Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32...

3188
来自专栏ml

HDUOJ -----1686

Oulipo Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

2857
来自专栏机器学习入门

LWC 62:743. Network Delay Time

LWC 62:743. Network Delay Time 传送门:743. Network Delay Time Problem: There are N...

2138
来自专栏算法修养

POJ-1125 Stockbroker Grapevine

Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Sub...

2884
来自专栏计算机视觉与深度学习基础

Leetcode 169 Majority Element

Given an array of size n, find the majority element. The majority element is th...

1709
来自专栏数据结构与算法

BZOJ1468: Tree

Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描...

3139
来自专栏算法修养

浙江工业大学校赛 小M和天平

小M和天平 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

2866
来自专栏ml

hdu 4034 Graph (floyd的深入理解)

Graph Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Jav...

34211
来自专栏calmound

动态规划集合

动态规划,少说也做了,30 40道了但是感觉还是没有入门,接下来一星期将重新做动态规划,hdu入门的,uva入门的,外加poj的,把动态规划都重新学一下 01背...

3146
来自专栏HansBug's Lab

3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

3158

扫码关注云+社区