月薪100万，你能接受996吗?

哎昨天刷抖音看到一个话题，那个——“月薪一百万你能接受996吗？”，我当时人都愣了。

你想啊，一百万一个月，这不是工资，这是续命费啊。就这价位，别说996了，997我都得笑着上班去，累晕在工位上都要喊一句“公司是我家”。

不过话又说回来，真要是月薪一百万，我估计也不敢辞职。怕啥？怕银行短信少一个零，怕领导半夜发消息我没秒回。你想想，一百万意味着啥？那就是每天工资三万多，打个喷嚏都是几百块。

算法题：隔离病毒

隔离病毒这道…嗯，怎么说呢，就是给你一张网格，1 代表被感染，0 代表健康。每天我们只能“围堵”一个最危险的病毒簇——就是那个如果今天不拦，明天能感染最多健康格子的那一团。围上墙之后，这一团就被永久隔离，别的簇还会继续扩散。目标是算出一共砌了多少面墙。听着有点像小区封控那味儿，对吧。

我昨晚十一点多在公司楼下抽烟…啊不对，说正事。网格是 4 邻接。所谓“簇”就是一堆 1 连成片。对每个簇我们要算两个量：它的“边界墙数”（和 0 相邻的边数）还有“威胁集合”（它明天能染到的 0 的集合）。每一轮选威胁集合最大的那个簇，把它的边界墙数加进答案，然后把那一簇标成“已隔离”，其它簇就把自己的威胁集合全部感染成 1，进入下一轮。直到再也没有 1 能扩散为止。

思路&实现

实现上…我用 DFS/BFS 分出所有簇；每个簇临时用 visited 标记，并用两个集合记录：neighbors（威胁 0 的坐标），walls（边界边数）。选最大的 neighbors 的簇隔离：把该簇的格子标成 -1 表示“封死”。剩下簇把 neighbors 全部置 1。重复。细节上注意：neighbors 要用坐标去重，否则墙数和威胁大小都会算错。还有，记得每一轮 visited 都要清空，不然会串场。

下面 Java 版本，能过主流数据范围，代码我尽量收紧了：

import java.util.*;

publicclassSolution{
privatestaticfinalint[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

publicintcontainVirus(int[][] grid){
int m = grid.length, n = grid[0].length;
int ans = 0;
while (true) {
            List<List<int[]>> comps = new ArrayList<>();
            List<Set<Integer>> threats = new ArrayList<>();
            List<Integer> walls = new ArrayList<>();
boolean[][] vis = newboolean[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !vis[i][j]) {
                        List<int[]> cells = new ArrayList<>();
                        Set<Integer> nei = new HashSet<>();
int[] wallCnt = {0};
                        dfs(grid, i, j, vis, cells, nei, wallCnt);
                        comps.add(cells);
                        threats.add(nei);
                        walls.add(wallCnt[0]);
                    }
                }
            }
if (comps.isEmpty()) break;

// 选威胁最大的簇
int pick = -1, best = 0;
for (int i = 0; i < threats.size(); i++) {
if (threats.get(i).size() > best) {
                    best = threats.get(i).size();
                    pick = i;
                }
            }
if (best == 0) break; // 没有可扩散

// 砌墙并隔离选中的簇
            ans += walls.get(pick);
for (int[] c : comps.get(pick)) grid[c[0]][c[1]] = -1;

// 其余簇扩散
for (int i = 0; i < threats.size(); i++) {
if (i == pick) continue;
for (int key : threats.get(i)) {
int x = key / n, y = key % n;
if (grid[x][y] == 0) grid[x][y] = 1;
                }
            }
        }
return ans;
    }

privatevoiddfs(int[][] g, int x, int y, boolean[][] vis,
                     List<int[]> cells, Set<Integer> nei, int[] wallCnt){
        vis[x][y] = true;
        cells.add(newint[]{x, y});
int m = g.length, n = g[0].length;
for (int[] d : DIRS) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (g[nx][ny] == 0) {
                wallCnt[0]++;
                nei.add(nx * n + ny);
            } elseif (g[nx][ny] == 1 && !vis[nx][ny]) {
                dfs(g, nx, ny, vis, cells, nei, wallCnt);
            }
        }
    }
}

就这样，思路不复杂，但实现要小心三个坑：威胁坐标去重、每轮重置访问标记、以及把被隔离簇标成 -1（不然会继续扩散）。我先去泡杯咖啡…你跑下样例就懂了。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html