6941 2023. 12. 20 21:03:43 Valaki2 Útépítés cpp17 Elfogadva 100/100 402ms 9352 KiB
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3","unroll-loops")
//#pragma GCC target("avx2")

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 200;

int n, m;
char table[1 + maxn][1 + maxn];
vector<pair<pii, int> > graph[1 + maxn][1 + maxn];
pair<pii, int> pr[1 + maxn][1 + maxn];
bool vis[1 + maxn][1 + maxn];
int edge_cnt;
bool in_matching[1 + maxn * maxn];
bool prepaired[1 + maxn][1 + maxn];

bool dfs(pii cur) {
    if(vis[cur.fi][cur.se]) {
        return false;
    }
    vis[cur.fi][cur.se] = true;
    for(pair<pii, int> nei : graph[cur.fi][cur.se]) {
        if(pr[nei.fi.fi][nei.fi.se].se == 0 || dfs(pr[nei.fi.fi][nei.fi.se].fi)) {
            pr[nei.fi.fi][nei.fi.se] = mp(cur, nei.se);
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> table[i][j];
            if(table[i][j] == '.') {
                continue;
            }
            pii a, b;
            if(table[i][j] == '/') {
                a = mp(i - 1, j);
                b = mp(i, j - 1);
            }
            if(table[i][j] == '\\') {
                a = mp(i - 1, j - 1);
                b = mp(i, j);
            }
            edge_cnt++;
            if(a.fi % 2 == 1) {
                swap(a, b);
            }
            graph[a.fi][a.se].pb(mp(b, edge_cnt));
        }
    }
    for(int i = 1; i <= n; i += 2) {
        for(int j = 0; j <= m; j++) {
            pr[i][j] = mp(mp(-1, -1), 0);
        }
    }
    int matching_size = 0;
    for(int i = 0; i <= n; i += 2) {
        for(int j = 0; j <= m; j++) {
            for(pair<pii, int> nei : graph[i][j]) {
                if(pr[nei.fi.fi][nei.fi.se].se == 0) {
                    //cout << i << " " << j << " - " << nei.fi.fi << " " << nei.fi.se << "\n";
                    pr[nei.fi.fi][nei.fi.se] = mp(mp(i, j), nei.se);
                    matching_size++;
                    prepaired[i][j] = true;
                    break;
                }
            }
        }
    }
    for(int i = 0; i <= n; i += 2) {
        for(int j = 0; j <= m; j++) {
            if(prepaired[i][j]) {
                continue;
            }
            for(int i2 = 0; i2 <= n; i2 += 2) {
                for(int j2 = 0; j2 <= m; j2++) {
                    vis[i2][j2] = false;
                }
            }
            if(dfs(mp(i, j))) {
                matching_size++;
            }
        }
    }
    cout << matching_size << "\n";
    for(int i = 1; i <= n; i += 2) {
        for(int j = 0; j <= m; j++) {
            int idx = pr[i][j].se;
            if(idx != 0) {
                in_matching[idx] = true;
            }
        }
    }
    int cur_edge = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(table[i][j] == '.') {
                cout << '.';
            } else {
                cur_edge++;
                if(in_matching[cur_edge]) {
                    cout << table[i][j];
                } else {
                    cout << '.';
                }
            }
        }
        cout << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while(T--) {
        solve();
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 4ms 3896 KiB
2 Elfogadva 0/0 14ms 6464 KiB
3 Elfogadva 5/5 3ms 4388 KiB
4 Elfogadva 5/5 3ms 4344 KiB
5 Elfogadva 5/5 3ms 4616 KiB
6 Elfogadva 5/5 4ms 5056 KiB
7 Elfogadva 5/5 3ms 4764 KiB
8 Elfogadva 5/5 4ms 5048 KiB
9 Elfogadva 5/5 4ms 5196 KiB
10 Elfogadva 5/5 4ms 5300 KiB
11 Elfogadva 5/5 4ms 5896 KiB
12 Elfogadva 5/5 4ms 6044 KiB
13 Elfogadva 5/5 4ms 6132 KiB
14 Elfogadva 5/5 4ms 6464 KiB
15 Elfogadva 5/5 6ms 6768 KiB
16 Elfogadva 5/5 14ms 7712 KiB
17 Elfogadva 5/5 16ms 9352 KiB
18 Elfogadva 5/5 79ms 8288 KiB
19 Elfogadva 5/5 25ms 8084 KiB
20 Elfogadva 5/5 13ms 9000 KiB
21 Elfogadva 5/5 13ms 8956 KiB
22 Elfogadva 5/5 402ms 9156 KiB