240302026-02-03 18:07:37algoproÚtépítéscpp17Time limit exceeded 90/100899ms4456 KiB
// UUID: 0a5733ae-bec5-46e9-bc64-a0be105aedef
#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;
    for(int i = 0; i <= n ; i++){
        for(int j= 0; j <= m; j+=2){
            volte.assign((n+1)*(m+1),0);
            int r = i*(m+1)+j;
            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
*/
SubtaskSumTestVerdictTimeMemory
base90/100
1Accepted0/01ms316 KiB
2Accepted0/010ms2988 KiB
3Accepted5/51ms316 KiB
4Accepted5/51ms316 KiB
5Accepted5/51ms316 KiB
6Accepted5/51ms316 KiB
7Accepted5/51ms316 KiB
8Accepted5/51ms316 KiB
9Accepted5/51ms316 KiB
10Accepted5/51ms316 KiB
11Accepted5/52ms564 KiB
12Accepted5/51ms564 KiB
13Accepted5/52ms580 KiB
14Accepted5/52ms564 KiB
15Accepted5/54ms1332 KiB
16Accepted5/5158ms4456 KiB
17Time limit exceeded0/5899ms3916 KiB
18Time limit exceeded0/5899ms3500 KiB
19Accepted5/532ms2992 KiB
20Accepted5/514ms4012 KiB
21Accepted5/514ms4012 KiB
22Accepted5/57ms2928 KiB