10602 2024. 04. 06 13:19:48 szil Útépítés cpp17 Elfogadva 100/100 712ms 9368 KiB
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 205*205;

vector<int> g[MAXN];
bool vis[MAXN], bad[MAXN];
char mp[205][205];
int n, m, mt[MAXN], col[MAXN];

int to_index(int i, int j) {
    return i*(m+1)+j;
}

void dfs(int u, int d = 0) {
    if (col[u] != -1) return;
    col[u] = d&1;
    for (int v : g[u]) {
        dfs(v, d+1);
    }
}

bool try_kuhn(int u) {
    if (vis[u]) return false;
    vis[u] = true;
    for (int v : g[u]) {
        if (mt[v] == -1 || try_kuhn(mt[v])) {
            mt[u] = v;
            mt[v] = u;
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            mp[i][j] = '.';
            char c; cin >> c;
            if (c == '\\') {
                int u = to_index(i-1, j-1), v = to_index(i, j);
                g[u].emplace_back(v);
                g[v].emplace_back(u);
            } else if (c == '/') {
                int u = to_index(i, j-1), v = to_index(i-1, j);
                g[u].emplace_back(v);
                g[v].emplace_back(u);
            }
        }
    }
    fill(col, col+MAXN, -1);
    fill(mt, mt+MAXN, -1);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dfs(to_index(i, j));
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (!g[to_index(i, j)].empty() && col[to_index(i, j)] & 1) {
                fill(vis, vis+MAXN, false);
                ans += try_kuhn(to_index(i, j));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int x = to_index(i, j);
            if (mt[x] != -1 && x >= mt[x]) {
                if (x-mt[x] > m) mp[i][j] = '\\';
                else mp[i][j+1] = '/';
            }
        }
    }
    cout << ans << "\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << mp[i][j];
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 4ms 4660 KiB
2 Elfogadva 0/0 37ms 6904 KiB
3 Elfogadva 5/5 3ms 5060 KiB
4 Elfogadva 5/5 3ms 5020 KiB
5 Elfogadva 5/5 3ms 5016 KiB
6 Elfogadva 5/5 3ms 5028 KiB
7 Elfogadva 5/5 4ms 5280 KiB
8 Elfogadva 5/5 4ms 5496 KiB
9 Elfogadva 5/5 4ms 5768 KiB
10 Elfogadva 5/5 4ms 5668 KiB
11 Elfogadva 5/5 6ms 5860 KiB
12 Elfogadva 5/5 6ms 6180 KiB
13 Elfogadva 5/5 6ms 6080 KiB
14 Elfogadva 5/5 4ms 6204 KiB
15 Elfogadva 5/5 14ms 6828 KiB
16 Elfogadva 5/5 81ms 9072 KiB
17 Elfogadva 5/5 712ms 9060 KiB
18 Elfogadva 5/5 27ms 8536 KiB
19 Elfogadva 5/5 28ms 7792 KiB
20 Elfogadva 5/5 43ms 9036 KiB
21 Elfogadva 5/5 45ms 9368 KiB
22 Elfogadva 5/5 19ms 8976 KiB