2025牛客暑期多校训练营5_J

2025牛客暑期多校训练营5_J

时限:\(2s\)
内存:\(512MB\)

题目描述

给定一个 \(n×m\) 的二元矩阵，其中 \(1\) 代表黑色单元格，\(0\) 代表白色单元格。每一秒，每个黑色单元格会将其上、下、左、右四个相邻的白色单元格变为黑色。

你可以将最多一个白色单元格变为黑色（将 \(0\) 变为 \(1\)），以最小化整个矩阵完全变黑所需的时间。求出这个最短时间。

---

输入格式

• 第一行包含两个整数 \(n\) 和 \(m\) (\(1 ≤ n×m ≤ 2×10^5\))，表示矩阵的行数和列数。
• 接下来的 \(n\) 行，每行包含 \(m\) 个数字（\(0\) 或 \(1\)），表示矩阵的初始状态。

---

输出格式

输出一个整数，表示在增加一个黑色单元格后，使整个矩阵变黑所需的最短时间。

---

思路

看到 \(1 \leq n×m \leq 2×10^5\)
时限只有 \(2s\)，因此可以预见应该是\(O(nm)\) 或者是 \(O(nm \log(X))\) 的复杂度。

由于我们肯定要算出每一个白点最早被染黑的时间，得做多源BFS，我们显然不能枚举每一个白点BFS,只能做一次。

即使在不加点的最坏情况下,

---

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

开始写check
我们可以得到每个白点被染黑的时间 \(t_i\)，我们应该要让所有\(t_i > T\)的点变成\(t_i \leq T\),之后称为慢点，

找出所有慢点组成的集合
\(E = {p: Time(p) > T}\)，即在 \(T\) 秒内无法被原有黑点染黑的点。
这些点必须依赖新加的黑点 \(c(i,j)\) 才能及时变黑。

即存在一个白点\(c(i,j)\)，对于每个 \(p \in E\)，要求

\[|p_x - i| + |p_y - j| \leq T \]

即 \(c\) 到 \(p\) 的曼哈顿距离不超过 \(T\)。
这等价于 \(c\) 必须落在以 \(p\) 为中心、半径 \(T\) 的菱形内。

可以将绝对值拆掉，得到四个不等式：

\[p_x -i - p_y + j \leq T \]

\[p_x -i + p_y - j \leq T \]

\[-p_x + i - p_y + j \leq T \]

\[-p_x + i + p_y - j \leq T \]

将\(i\)和\(j\)作为变量，移项得到:

\[i+j \in [p_x + p_y - T,, p_x + p_y + T] \]

\[i-j \in [p_x - p_y - T,, p_x - p_y + T] \]

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

\[i+j \in [L_1, R_1] \]

\[i-j \in [L_2, R_2] \]

其中

\[L_1 = \max_{p \in E}(p_x + p_y - T) \]

\[R_1 = \min_{p \in E}(p_x + p_y + T) \]

\[L_2 = \max_{p \in E}(p_x - p_y - T) \]

\[R_2 = \min_{p \in E}(p_x - p_y + T) \]

可以\(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\) 秒内全部染黑。
如果 \(E\) 为空（即所有点本来就能在 \(T\) 秒内变黑），直接返回true。

复杂度 \(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;
}