240372026-02-03 18:15:55algoproÚtépítéscpp17Elfogadva 100/100323ms4344 KiB
// UUID: ca99da23-55cb-43a7-a6cf-d0120b22e596
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<pair<int,int>>>adj;
vector<bool>elek;
vector<pair<int,char>>elek2;
vector<bool>foglalt;
vector<bool>volte;

template<typename t1, typename t2>
std::ostream& operator<<(std::ostream& os, std::pair<t1,t2>p ){
    
    os << p.first << ' ' << p.second << "; ";
    return os;
}

template<class t>
std::ostream& operator<<(std::ostream& os, std::vector<t>v){
    for(t a : v){
        os << a<< " ";
    }
    os << "\n";
    return os;
}

bool dfs(int cs, bool prev = 1){
    if(!foglalt[cs] && !prev){
        foglalt[cs] = 1;
        return 1;
    }
    volte[cs] = 1;
    for(auto [i,el] : adj[cs]){
        if((elek[el] xor prev) && !volte[i]){
            if(dfs(i,!prev)){
                elek[el] = !elek[el];
                //cout << cs << " ";
                return 1;
            }
        }
    }
    return 0;
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    adj.assign((n+1)*(m+1),vector<pair<int,int>>());
    foglalt.assign((n+1)*(m+1),0);
    volte.assign((n+1)*(m+1),0);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            if(c == '/'){
                m++;
               
                adj[i*m+j+1].push_back({i*m+j+m, elek2.size()});
                adj[i*m+j+m].push_back({i*m+j+1, elek2.size()});
                m--;
                elek2.push_back({i*m+j, c});
            }else if(c == '\\'){
                m++;
                adj[i*m+j].push_back({i*m+j+m+1, elek2.size()});
                adj[i*m+j+m+1].push_back({i*m+j, elek2.size()});
                m--;
                elek2.push_back({i*m+j, c});
            }
        }
    }
    elek.assign(elek2.size(),0);

    
    int ans = 0;
    vector<int>sor((n+1)*(m+1));
    iota(sor.begin(),sor.end(),0);
    //cout << sor ;
    random_shuffle(sor.begin(), sor.end());
    for(int r : sor){
        //int r = i*(m+1)+j;
        if(foglalt[r])continue;
        volte.assign((n+1)*(m+1),0);
        if(dfs(r)){
            ans++;
            foglalt[r] = 1;
        }
    }
    cout << ans << endl;
    vector<string>b(n,string(m, '.'));
    for(int i = 0; i < elek.size(); i++ ){
        if(elek[i]){
            b[elek2[i].first/m][elek2[i].first%m] = elek2[i].second;
        }
    }
    for(auto s : b){
        cout << s << '\n';
    }
}
/*
1 2 1
1 2
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/016ms3440 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva5/51ms508 KiB
8Elfogadva5/51ms316 KiB
9Elfogadva5/51ms316 KiB
10Elfogadva5/51ms508 KiB
11Elfogadva5/52ms564 KiB
12Elfogadva5/51ms564 KiB
13Elfogadva5/52ms564 KiB
14Elfogadva5/52ms824 KiB
15Elfogadva5/54ms1336 KiB
16Elfogadva5/517ms3472 KiB
17Elfogadva5/514ms3740 KiB
18Elfogadva5/5323ms4344 KiB
19Elfogadva5/517ms3456 KiB
20Elfogadva5/518ms4268 KiB
21Elfogadva5/523ms4264 KiB
22Elfogadva5/514ms2736 KiB