题解：ABC427E Wind Cleaning【BFS】

chenwenmo · 2025-10-12 14:40:02 · 题解

ABC427E Wind Cleaning

根据相对运动，所有 # 一起移动转换为只有 T 移动。

看这题的第一眼是状态数为 O(n^2) 的 BFS，但如果直接这样做，相当于 # 出界了之后还可以再回来，而题目要求出界后就被删去了。

那么考虑我们还需要哪些状态才能刻画这一情况。发现只需记录当前所有 # 的 \min x,\max x,\min y,\max y 即可，若当前某个 # (x,y) 满足 x\in[\min x,\max x],y\in[\min y,\max y]，那么该 # 还没被删去，否则已经被删去。

因此写一个 O(n^6) 的 BFS 即可。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UI = unsigned int;
using ULL = unsigned long long;
using DB = double;
using LDB = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define CP(x) complex<x>
#define fst first
#define snd second
#define popcnt(i) __builtin_popcount(i)

const int N = 60, C = 20;

int n, m, d[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
bool rec[N][N];

struct Info {
    int x, y, minX, maxX, minY, maxY, c;
} s;
map<array<int, 6>, bool> vis;

void chkmax(int &a, int b) { if (b > a) a = b; }

void chkmin(int &a, int b) { if (b < a) a = b; }

bool exist(Info u, int x, int y) {
    return (x >= u.minX && x <= u.maxX && y >= u.minY && y <= u.maxY);
}

bool check(Info u) {
    int dx = u.x - s.x, dy = u.y - s.y;
    for (int i = 1 + dx; i <= n + dx; i++) {
        for (int j = 1 + dy; j <= m + dy; j++) {
            if (rec[i + C][j + C] && exist(u, i, j)) return 0;
        }
    }
    return 1;
}

void update(Info u, Info &v) {
    v.c = u.c + 1;
    v.maxX = v.maxY = 0;
    v.minX = n + 1, v.minY = m + 1;
    int dx = v.x - s.x, dy = v.y - s.y;
    for (int i = 1 + dx; i <= n + dx; i++) {
        for (int j = 1 + dy; j <= m + dy; j++) {
            if (rec[i + C][j + C] && exist(u, i, j)) {
                chkmax(v.maxX, i);
                chkmax(v.maxY, j);
                chkmin(v.minX, i);
                chkmin(v.minY, j);
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    char c;
    s = {0, 0, n + 1, 0, m + 1, 0, 0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c;
            if (c == 'T') {
                s.x = i, s.y = j;
            } else if (c == '#') {
                rec[i + C][j + C] = 1;
                chkmax(s.maxX, i);
                chkmax(s.maxY, j);
                chkmin(s.minX, i);
                chkmin(s.minY, j);
            }
        }
    }
    queue<Info> q;
    q.push(s);
    vis[{s.x, s.y, s.maxX, s.minX, s.maxY, s.minY}] = 1;
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        if (check(u)) {
            cout << u.c << '\n';
            return;
        }
        Info v;
        for (int i = 0; i < 4; i++) {
            v.x = u.x + d[i][0], v.y = u.y + d[i][1];
            if (rec[v.x + C][v.y + C] && exist(u, v.x, v.y)) continue;
            update(u, v);
            if (vis.count({v.x, v.y, v.maxX, v.minX, v.maxY, v.minY})) continue;
            vis[{v.x, v.y, v.maxX, v.minX, v.maxY, v.minY}] = 1;
            q.push(v);
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}