5342 2023. 04. 26 07:55:44 sztomi Útépítés cpp11 Elfogadva 100/100 751ms 9996 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define sor first
#define oszlop second

const int MAXPONTDB = 201*201;

int n, m;
int pont_db;
vector<int> graf[MAXPONTDB];
bool volt[MAXPONTDB]{false};
bool szin[MAXPONTDB]{false};
int par[MAXPONTDB];

int hely_to_ind(pii p){
    return p.sor * (m+1) + p.oszlop;
}

pii ind_to_hely(int ind){
    return {ind / (m+1), ind % (m+1)};
}

void szinez(int akt, bool s=false){
    volt[akt] = true;
    szin[akt] = s;
    s = !s;
    for(int kov : graf[akt]){
        if(volt[kov]) continue;
        szinez(kov, s);
    }
}

bool par_keres(int akt){
    if(volt[akt]) return false;
    volt[akt] = true;
    for(int kov : graf[akt]){
        if(par[kov] == -1 || par_keres(par[kov])){
            par[kov] = akt;
            volt[akt] = false;
            return true;
        }
    }
    volt[akt] = false;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // maximal bipartite matching
    // sakktabla szinezes eseten egy el mindig azonos szinueket kot ossze
    cin >> n >> m;
    pont_db = (n+1) * (m+1);
    char c;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> c;
            if(c == '/'){
                int a = hely_to_ind({i+1, j});
                int b = hely_to_ind({i, j+1});
                graf[a].push_back(b);
                graf[b].push_back(a);
            }
            else if(c == '\\'){
                int a = hely_to_ind({i, j});
                int b = hely_to_ind({i+1, j+1});
                graf[a].push_back(b);
                graf[b].push_back(a);
            }
        }
    }


    for(int i = 0; i < pont_db; i++){
        if(!volt[i]) szinez(i);
    }

/*
    for(int i = 0; i < pont_db; i++){
        pii hely = ind_to_hely(i);
        cout << i << " (" << hely.first << ", " << hely.second << ") szin: " << szin[i] << ": ";
        for(int x : graf[i]){
            cout << x << ", ";
        }
        cout << "\n";
    }
*/

    fill(par, par+pont_db, -1);
    fill(volt, volt+pont_db, false);
    for(int i = 0;  i < pont_db; i++){
        if(szin[i] && par[i] == -1){
            //cout << "indit: " << i << "\n";
            par_keres(i);
        }
    }

/*
    for(int i = 0; i < pont_db; i++){
        cout << i << ": " << par[i] << "\n";
    }
*/
    int db = 0;
    vector<vector<char>> ki(n, vector<char>(m, '.'));
    for(int i = 0; i < pont_db; i++){
        if(par[i] != -1){
            db++;
            pii a = ind_to_hely(i);
            pii b = ind_to_hely(par[i]);
            pii hely = {min(a.sor, b.sor), min(a.oszlop, b.oszlop)};
/*
            cout << "a: " << a.sor << " " << a.oszlop << "\n";
            cout << "b: " << b.sor << " " << b.oszlop << "\n";
            cout << "hely: " << hely.sor << " " << hely.oszlop << "\n";
*/
            if(a == hely || b == hely){
                ki[hely.sor][hely.oszlop] = '\\';
            }
            else{
                ki[hely.sor][hely.oszlop] = '/';
            }
        }
    }

    cout << db << "\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << ki[i][j];
        }
        cout << "\n";
    }

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 4ms 3960 KiB
2 Elfogadva 0/0 12ms 6772 KiB
3 Elfogadva 5/5 4ms 4488 KiB
4 Elfogadva 5/5 3ms 4592 KiB
5 Elfogadva 5/5 4ms 4732 KiB
6 Elfogadva 5/5 3ms 4972 KiB
7 Elfogadva 5/5 3ms 4916 KiB
8 Elfogadva 5/5 3ms 5324 KiB
9 Elfogadva 5/5 3ms 5496 KiB
10 Elfogadva 5/5 3ms 5352 KiB
11 Elfogadva 5/5 4ms 5816 KiB
12 Elfogadva 5/5 4ms 5916 KiB
13 Elfogadva 5/5 4ms 5792 KiB
14 Elfogadva 5/5 4ms 5992 KiB
15 Elfogadva 5/5 6ms 6412 KiB
16 Elfogadva 5/5 64ms 9412 KiB
17 Elfogadva 5/5 751ms 9740 KiB
18 Elfogadva 5/5 9ms 9996 KiB
19 Elfogadva 5/5 16ms 8288 KiB
20 Elfogadva 5/5 14ms 9348 KiB
21 Elfogadva 5/5 14ms 9300 KiB
22 Elfogadva 5/5 8ms 9296 KiB