2025牛客暑期多校訓練營5 J.Fastest Coverage Problem

時限:\(2s\)
內(nèi)存:\(512MB\)

題目描述

給定一個 \(n×m\) 的二元矩陣，其中 \(1\) 代表黑色單元格，\(0\) 代表白色單元格。每一秒，每個黑色單元格會將其上、下、左、右四個相鄰的白色單元格變?yōu)楹谏?/p>

你可以將最多一個白色單元格變?yōu)楹谏▽?\(0\) 變?yōu)?\(1\)），以最小化整個矩陣完全變黑所需的時間。求出這個最短時間。

輸入格式

• 第一行包含兩個整數(shù) \(n\) 和 \(m\) (\(1 ≤ n×m ≤ 2×10^5\))，表示矩陣的行數(shù)和列數(shù)。
• 接下來的 \(n\) 行，每行包含 \(m\) 個數(shù)字（\(0\) 或 \(1\)），表示矩陣的初始狀態(tài)。

輸出格式

輸出一個整數(shù)，表示在增加一個黑色單元格后，使整個矩陣變黑所需的最短時間。

思路

看到 \(1 \leq n×m \leq 2×10^5\)
時限只有 \(2s\)，因此可以預(yù)見應(yīng)該是\(O(nm)\) 或者是 \(O(nm \log(X))\) 的復(fù)雜度。

由于我們肯定要算出每一個白點最早被染黑的時間，得做多源BFS，我們顯然不能枚舉每一個白點BFS,只能做一次。

即使在不加點的最壞情況下,

現(xiàn)在做完BFS后，答案一定 \(T \leq n+m\),
且一定在 \([0, t_{max}]\) 之間，考慮二分 \(T\)。

開始寫check
我們可以得到每個白點被染黑的時間 \(t_i\)，我們應(yīng)該要讓所有\(t_i > T\)的點變成\(t_i \leq T\),之后稱為慢點，

找出所有慢點組成的集合
\(E = {p: Time(p) > T}\)，即在 \(T\) 秒內(nèi)無法被原有黑點染黑的點。
這些點必須依賴新加的黑點 \(c(i,j)\) 才能及時變黑。

即存在一個白點\(c(i,j)\)，對于每個 \(p \in E\)，要求

即 \(c\) 到 \(p\) 的曼哈頓距離不超過 \(T\)。
這等價于 \(c\) 必須落在以 \(p\) 為中心、半徑 \(T\) 的菱形內(nèi)。

可以將絕對值拆掉，得到四個不等式：

將\(i\)和\(j\)作為變量，移項得到:

那么所有慢點的交集就是：

其中

可以\(O(nm)\)地計算出 \(L_1, R_1, L_2, R_2\)。

之后就是只要找到一個這樣的點就可以了。
也可以\(O(nm)\)地遍歷所有白點。
只要存在一個原本為白色的格子 \((i, j)\)，滿足 \(i+j \in [L_1, R_1]\) 且 \(i-j \in [L_2, R_2]\)，就可以在 \(T\) 秒內(nèi)全部染黑。
如果 \(E\) 為空（即所有點本來就能在 \(T\) 秒內(nèi)變黑），直接返回true。

復(fù)雜度 \(O(nm\log(nm))\)，

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> mp(n, vector<int>(m));
    const int INF = 1e9;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mp[i][j];

    vector<vector<int>> D(n, vector<int>(m, INF));
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 1)
            {
                D[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (auto &d : dirs)
        {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && D[nx][ny] > D[x][y] + 1)
            {
                D[nx][ny] = D[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    int tm = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            tm = max(tm, D[i][j]);
        }
    }

    auto letmeseesee = [&](int T) -> bool
    {
        int L1 = -1e9, R1 = 1e9, L2 = -1e9, R2 = 1e9;

        bool ok = false;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (D[i][j] > T)
                {
                    ok = true;
                    L1 = max(L1, i + j - T);
                    R1 = min(R1, i + j + T);
                    L2 = max(L2, i - j - T);
                    R2 = min(R2, i - j + T);
                }
            }
        }

        if (!ok)
            return 1;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mp[i][j] == 0)
                {
                    int sum = i + j, diff = i - j;
                    if (sum >= L1 && sum <= R1 && diff >= L2 && diff <= R2)
                        return 1;
                }
            }
        }
        return 0;
    };

    int lo = 0, hi = tm;
    int ans = hi;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (letmeseesee(mid))
        {
            ans = mid;
            hi = mid - 1;
        }
        else
        {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";

    return 0;
}