题解：P5532 [CCO2019] Sirtet

· · 题解

纪念一下在模拟赛中赛时唯一过的一道题，喜提倒数不知道多少名 :)

不需要差分约束的做法，没有 \log。

考虑把图上的每个位置看成一个点，我们考虑直接算出每个 # 点会下落多少高度。

首先如果是在一个连通块里的，可以直接连边权为 0 的边，因为肯定是一起停止的，下落高度相同。可以 DFS 处理，时间复杂度 \mathcal O(nm)。

然后应该怎么做呢？模拟下落操作，对于形如下面的东西：

.
.

和

#
.

都需要下落，所以我们考虑从上往下连一条边权为 1 的边。而对于：

.
#

就直接停住了。所以从上往下连一条边权为 0 的边。

因为停止是算最先停住的位置，连完之后跑一个最短路就好了。但是边权只有 0 和 1，直接 01BFS，可以做到整体 \mathcal O(nm)。

namespace liuzimingc {
#define endl '\n'
#define pii pair<int, int>
const int N = 1e6 + 5, INF = 1e9;
const int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };

int n, m, tot, dis[N];
bool vis[N], id[N];
vector<int> v;
vector<char> s[N], ans[N];
deque<pii> q;
vector<pii> e[N];
char str[N];

int get(int x, int y) { return (x - 1) * m + y; }

void dfs(int x, int y, int lst) {
    id[get(x, y)] = true;
    if (lst) e[lst].push_back({ get(x, y), 0 }), e[get(x, y)].push_back({ lst, 0 });
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m || id[get(nx, ny)] || s[nx][ny] == '.') continue;
        dfs(nx, ny, get(x, y));
    }
}

void bfs() {
    for (int i = 1; i <= n * m; i++) dis[i] = INF;
    for (int i = 1; i <= m; i++) q.push_back({ get(n, i), 0 });
    while (q.size()) {
        int u = q.front().first, d = q.front().second; q.pop_front();
        if (vis[u]) continue;
        vis[u] = true;
        dis[u] = d;
        for (const auto &i : e[u]) {
            int v = i.first, w = i.second;
            if (!w) q.push_front({ v, d });
            else q.push_back({ v, d + 1 });
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        s[i].resize(m + 1);
        ans[i].resize(m + 1);
        cin >> (str + 1);
        for (int j = 1; j <= m; j++) s[i][j] = str[j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!id[get(i, j)] && s[i][j] == '#') dfs(i, j, 0);
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            if (s[i + 1][j] == '.') e[get(i + 1, j)].push_back({ get(i, j), 1 });
            else if (s[i][j] == '.') e[get(i + 1, j)].push_back({ get(i, j), 0 });
    bfs();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (s[i][j] == '#') ans[i + dis[get(i, j)]][j] = '#';
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << (ans[i][j] ? ans[i][j] : '.');
    return 0;
}
} // namespace liuzimingc