53412023-04-26 07:48:27sztomiÚtépítéscpp11Futási hiba 5/10041ms64860 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){
    for(int kov : graf[akt]){
        if(par[kov] == -1 || par_keres(par[kov])){
            par[kov] = akt;
            return true;
        }
    }
    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);
    for(int i = 0;  i < pont_db; i++){
        if(szin[i] && par[i] == -1){
            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)};

            if(a == 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ÖsszpontTesztVerdiktIdőMemória
base5/100
1Elfogadva0/04ms3812 KiB
2Futási hiba0/034ms64860 KiB
3Futási hiba0/529ms64616 KiB
4Futási hiba0/532ms64372 KiB
5Futási hiba0/529ms64144 KiB
6Futási hiba0/529ms63908 KiB
7Futási hiba0/532ms63672 KiB
8Futási hiba0/529ms63668 KiB
9Futási hiba0/532ms63428 KiB
10Futási hiba0/537ms63324 KiB
11Futási hiba0/535ms63088 KiB
12Futási hiba0/532ms63068 KiB
13Futási hiba0/532ms63064 KiB
14Futási hiba0/532ms63040 KiB
15Futási hiba0/529ms63004 KiB
16Futási hiba0/534ms62980 KiB
17Futási hiba0/539ms62684 KiB
18Elfogadva5/59ms9900 KiB
19Futási hiba0/537ms62440 KiB
20Futási hiba0/534ms62428 KiB
21Futási hiba0/541ms62452 KiB
22Futási hiba0/537ms62164 KiB