2025-ICPC-Asia-Taiwan-Online-台湾网络赛-E. Explosive Slabstones Rearrangement（首先转化为知道值，判定可行性问题）（所有不需要推动者的推箱子问题，都是连通块问题） · znzryb
## 题目大意
巴巴拉有一个花园。这个花园可以表示为一个$n \times m$的网格。她在花园里放置了$k$块石板，这样她每天可以享受从一块石板跳到另一块石板。这些石板的索引从$1$到$k$。每块石板完全占据花园中的某个单元格，并且没有两块石板放置在同一个单元格上。
然而，一个邪恶的人，巴巴拉，打算放置一个特殊设备，它将占据花园中的一个矩形区域。如果任何石板与设备重叠，它将爆炸并摧毁整个花园！
为了避免爆炸，巴巴拉想通过在花园内移动石板来重新排列石板。**在重新排列石板期间**，石板应保持不重叠。花费的能量等于所有已移动的石板中最大的索引。现在，巴巴拉想知道重新排列石板所需的最小能量，这样她就可以为“其他目的”节省能量。
例如，假设设备将放置在蓝色矩形区域。然后，巴巴拉可以按以下方式重新排列石板。请注意，在整个过程中，石板不会重叠，不仅在重新排列之后。所有已移动的石板的索引最多为$4$，因此花费的能量为$4$。
_00977c3c.png)
## 思路讲解
## 判定 E 是否可行（check(E)）
1. **如果矩形里存在编号 > E 的石板**：它动不了，又在矩形里 ⇒ 直接不可行。
1. 在整张网格上，把**所有“编号 > E 的石板格子”删掉（当墙）**，对剩余格子做 BFS/DFS 求连通块。
1. 对每个连通块 $C$ 统计：
- $t(C)$：这个块里 **编号 <= E** 的石板数量（可移动棋子数）
- $s(C)$：这个块里 **不在矩形内** 的格子数量（最终可安置容量）
必须满足对所有块：$t(C) \le s(C)$
否则该连通块里有“多出来的棋子”无论怎么挪也得有人留在矩形里 ⇒ 不可行。
1. 单调性：E 越大，你能动的石板越多（墙越少），只会更容易可行 ⇒ 可以对 E 在 $[0,k]$ **二分最小可行值**。
对于一**连通块**，这个合法，其实就是$在炸弹区的石块数量≤炸弹区外空白数量$。
```cpp
auto bfs=[&](ll threshold,ll x,ll y) -> bool {
queue<pair<ll,ll>> q;
vis[x][y]=tim;
q.push({x,y});
ll block_in_cnt=0,space_cnt=0;
while (!q.empty()) {
auto [px,py]=q.front();
q.pop();
if (is_in(px,py)) {
if (maze[px][py]>0) {
block_in_cnt++;
}
}else {
if (maze[px][py]==0) {
space_cnt++;
}
}
for (int i=0;i<4;++i) {
ll tox=px+dx[i],toy=py+dy[i];
if (is_valid(threshold,tox,toy)) {
vis[tox][toy]=tim;
q.push({tox,toy});
}
}
}
if (space_cnt>=block_in_cnt) {
return true;
}
return false;
};
```
## AC代码
AC
[https://codeforces.com/gym/106084/submission/361123071](https://codeforces.com/gym/106084/submission/361123071)
::: 源代码
```cpp
/**
* Problem: E. Explosive Slabstones Rearrangement
* Contest: 2025 ICPC Asia Taiwan Online Programming Contest
* Judge: Codeforces
* URL: https://codeforces.com/gym/106084/problem/E
* Created: 2026-02-02 15:24:08
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
/* -> (Right, Down, Left, Up)
| |
<-
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void Solve() {
ll N,M,K;
cin >> N >> M >> K;
vector maze(N+2,vector<ll>(M+2));
for (int i=1;i<=K;++i) {
ll x,y;
cin>>x>>y;
maze[x][y]=i;
}
ll xl,yl,xr,yr;
cin>>xl>>yl>>xr>>yr;
ll mx_in=0;
for (int i=xl;i<=xr;++i) {
for (int j=yl;j<=yr;++j) {
mx_in=max(mx_in,maze[i][j]);
}
}
vector vis(N+2,vector<int>(M+2));
ll tim=0;
auto is_valid=[&](ll threshold,ll x,ll y) {
if (x<1 || x>N) {
return false;
}
if (y<1 || y>M) {
return false;
}
if (maze[x][y]>threshold) {
return false;
}
if (vis[x][y]>=tim) {
return false;
}
return true;
};
auto is_in=[&](ll x,ll y) {
if (x>=xl && x<=xr && y>=yl && y<=yr) {
return true;
}
return false;
};
auto bfs=[&](ll threshold,ll x,ll y) -> bool {
queue<pair<ll,ll>> q;
vis[x][y]=tim;
q.push({x,y});
ll block_in_cnt=0,space_cnt=0;
while (!q.empty()) {
auto [px,py]=q.front();
q.pop();
if (is_in(px,py)) {
if (maze[px][py]>0) {
block_in_cnt++;
}
}else {
if (maze[px][py]==0) {
space_cnt++;
}
}
for (int i=0;i<4;++i) {
ll tox=px+dx[i],toy=py+dy[i];
if (is_valid(threshold,tox,toy)) {
vis[tox][toy]=tim;
q.push({tox,toy});
}
}
}
if (space_cnt>=block_in_cnt) {
return true;
}
return false;
};
auto check=[&](ll threshold) -> bool {
tim++;
for (int i=1;i<=N;++i) {
for (int j=1;j<=M;++j) {
if (!is_valid(threshold,i,j)) {
continue;
}
if(!bfs(threshold,i,j)) {
return false;
}
}
}
return true;
};
ll l=mx_in,r=K;
while (l<r) {
ll mid=(l+r)>>1;
if (check(mid)) {
r=mid;
}else {
l=mid+1;
}
}
// #ifdef LOCAL
// debug(l);
// #endif
if (check(l)) {
cout<<l<<"\n";
}else {
cout<<-1<<"\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> lT;
// while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106084/submission/361123071
*/
```
:::
## 心路历程（WA，TLE，MLE……）