53422023-04-26 07:55:44sztomiÚtépítéscpp11Accepted 100/100751ms9996 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";
    }

}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/04ms3960 KiB
2Accepted0/012ms6772 KiB
3Accepted5/54ms4488 KiB
4Accepted5/53ms4592 KiB
5Accepted5/54ms4732 KiB
6Accepted5/53ms4972 KiB
7Accepted5/53ms4916 KiB
8Accepted5/53ms5324 KiB
9Accepted5/53ms5496 KiB
10Accepted5/53ms5352 KiB
11Accepted5/54ms5816 KiB
12Accepted5/54ms5916 KiB
13Accepted5/54ms5792 KiB
14Accepted5/54ms5992 KiB
15Accepted5/56ms6412 KiB
16Accepted5/564ms9412 KiB
17Accepted5/5751ms9740 KiB
18Accepted5/59ms9996 KiB
19Accepted5/516ms8288 KiB
20Accepted5/514ms9348 KiB
21Accepted5/514ms9300 KiB
22Accepted5/58ms9296 KiB