题解：CF1949J Amanda the Amoeba

james1BadCreeper · 2024-06-27 09:58:24 · 题解

我们考虑将初始状态和结束状态都移到一个相同的状态，然后将结束状态转到相同状态的过程反过来即可。

将一个状态转移到字典序最小的合法状态，初始时按照连通块的顺序给连通块内的点进行编号，每次将最大非割点转移到最小的可以空白位置即可。

#include <bits/stdc++.h>
using namespace std; 
const int N = 1e4 + 5; 
const int DX[] = {-1, 0, 1, 0}, DY[] = {0, 1, 0, -1}; 

int n, m; 
char s[55][55]; 
int c, p[55][55], x[N], y[N]; 
int mx, mn, tot, X1[N], Y1[N], X2[N], Y2[N]; 

inline bool ishe(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] != 'X'; 
}

void dfs1(int x, int y) {
    p[x][y] = ++c, ::x[c] = x, ::y[c] = y;
    for (int k = 0; k < 4; ++k) {
        int xx = x + DX[k], yy = y + DY[k]; 
        if (ishe(xx, yy) && !p[xx][yy]) dfs1(xx, yy); 
    }
}

int dfn[55][55], low[55][55], num; 
void tarjan(int x, int y, int fx, int fy) {
    dfn[x][y] = low[x][y] = ++num; 
    int c = (fx != 0); 
    for (int k = 0; k < 4; ++k) {
        int xx = x + DX[k], yy = y + DY[k]; 
        if (!ishe(xx, yy) || s[xx][yy] == '.') continue; 
        if (!dfn[xx][yy]) {
            tarjan(xx, yy, x, y); low[x][y] = min(low[x][y], low[xx][yy]); 
            if (dfn[x][y] <= low[xx][yy]) ++c; 
        } else low[x][y] = min(low[x][y], dfn[xx][yy]); 
    }
    if (c < 2) mx = max(mx, p[x][y]); 
}

int solve(void) {
    while (1) {
        mx = num = 0, mn = c + 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                if (s[i][j] == '*') {
                    if (!mx) tarjan(i, j, 0, 0), s[x[mx]][y[mx]] = '.'; 
                    if (s[i][j] == '*') {
                        for (int k = 0; k < 4; ++k) {
                            int xx = i + DX[k], yy = j + DY[k]; 
                            if (ishe(xx, yy) && s[xx][yy] == '.') mn = min(mn, p[xx][yy]); 
                        }
                    }
                }
                dfn[i][j] = low[i][j] = 0;
            }
        if (mx == mn) return mx; 
        ++tot; X1[tot] = x[mx]; Y1[tot] = y[mx]; X2[tot] = x[mn]; Y2[tot] = y[mn]; 
        s[x[mn]][y[mn]] = '*'; 
    }
}
int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> s[i] + 1; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (s[i][j] != 'X' && !p[i][j]) dfs1(i, j); 
    int id = solve(), _ = tot; 
    for (int i = 1; i <= n; ++i) cin >> s[i] + 1; 
    if (id != solve()) return cout << "NO\n", 0; 
    cout << "YES\n" << tot << "\n"; 
    for (int i = 1; i <= _; ++i) cout << X1[i] << ' ' << Y1[i] << ' ' << X2[i] << ' ' << Y2[i] << '\n'; 
    for (int i = tot; i > _; --i) cout << X2[i] << ' ' << Y2[i] << ' ' << X1[i] << ' ' << Y1[i] << '\n'; 
    return 0; 
}