2025-ICPC-Asia-Taiwan-Online-台湾网络赛-E. Explosive Slabstones Rearrangement（首先转化为知道值，判定可行性问题）（所有不需要推动者的推箱子问题，都是连通块问题）

题目大意

巴巴拉有一个花园。这个花园可以表示为一个$n \times m$的网格。她在花园里放置了$k$块石板，这样她每天可以享受从一块石板跳到另一块石板。这些石板的索引从$1$到$k$。每块石板完全占据花园中的某个单元格，并且没有两块石板放置在同一个单元格上。

然而，一个邪恶的人，巴巴拉，打算放置一个特殊设备，它将占据花园中的一个矩形区域。如果任何石板与设备重叠，它将爆炸并摧毁整个花园！

为了避免爆炸，巴巴拉想通过在花园内移动石板来重新排列石板。在重新排列石板期间，石板应保持不重叠。花费的能量等于所有已移动的石板中最大的索引。现在，巴巴拉想知道重新排列石板所需的最小能量，这样她就可以为“其他目的”节省能量。

例如，假设设备将放置在蓝色矩形区域。然后，巴巴拉可以按以下方式重新排列石板。请注意，在整个过程中，石板不会重叠，不仅在重新排列之后。所有已移动的石板的索引最多为$4$，因此花费的能量为$4$。

思路讲解

判定 E 是否可行（check(E)）

1. 如果矩形里存在编号 > E 的石板：它动不了，又在矩形里 ⇒ 直接不可行。

2. 在整张网格上，把所有“编号 > E 的石板格子”删掉（当墙），对剩余格子做 BFS/DFS 求连通块。

3. 对每个连通块 $C$ 统计：

• $t(C)$：这个块里 编号 <= E 的石板数量（可移动棋子数）

• $s(C)$：这个块里 不在矩形内 的格子数量（最终可安置容量）
  必须满足对所有块：$t(C) \le s(C)$
  否则该连通块里有“多出来的棋子”无论怎么挪也得有人留在矩形里 ⇒ 不可行。

1. 单调性：E 越大，你能动的石板越多（墙越少），只会更容易可行 ⇒ 可以对 E 在 $[0,k]$ 二分最小可行值。

对于一连通块，这个合法，其实就是$在炸弹区的石块数量≤炸弹区外空白数量$。

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

源代码

/**
 * 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……）