13132022-05-07 17:08:27k_balintÚtépítéscpp14Elfogadva 100/100542ms7492 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 40401;

int n, m;
int N,tt;
vector<int> g[MAXN+1];
int par[MAXN+1];
int vis[MAXN+1];
bool A[MAXN+1];

bool novel(int v){
    if(vis[v]==tt) return 0;
    vis[v]=tt;

    for(int x:g[v]){
        if(par[x]==-1 || novel(par[x])){
            par[v]=x; par[x]=v;
            return 1;
        }
    }
    return 0;
}

int magyar(){
    tt=0; int cnt=0;
    for(int i=0;i<N;i++){
        par[i]=-1;
    }

    for(int i=0;i<N;i++){
        if(A[i] && par[i]==-1){
            ++tt;
            cnt+=novel(i);
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m; N=(n+1)*(m+1);
    for(int i = 0; i < MAXN; i++){
        A[i]=i/(m+1)%2;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c; cin>>c;
            if(c == '/'){
                g[(i+1)*(m+1) + j].push_back(i*(m+1) + j+1);
                g[i*(m+1) + j+1].push_back((i+1)*(m+1) + j);
            }else if(c == '\\'){
                g[i*(m+1)+j].push_back((i+1)*(m+1)+j+1);
                g[(i+1)*(m+1)+j+1].push_back(i*(m+1)+j);
            }
        }
    }

    cout << magyar() << '\n';

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){

            if(par[i*(m+1)+j] == (i+1)*(m+1)+j+1){
                cout<<'\\';
            }

            else if(par[(i+1)*(m+1)+j] == i*(m+1)+j+1){
                cout<<'/';
            }

            else{
                cout << '.';
            }

        }
        cout << '\n';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/03ms3856 KiB
2Elfogadva0/09ms6564 KiB
3Elfogadva5/52ms3852 KiB
4Elfogadva5/52ms3856 KiB
5Elfogadva5/52ms3860 KiB
6Elfogadva5/52ms4024 KiB
7Elfogadva5/52ms3868 KiB
8Elfogadva5/52ms4012 KiB
9Elfogadva5/52ms4020 KiB
10Elfogadva5/52ms4020 KiB
11Elfogadva5/53ms4104 KiB
12Elfogadva5/53ms4100 KiB
13Elfogadva5/53ms4124 KiB
14Elfogadva5/54ms4268 KiB
15Elfogadva5/54ms4812 KiB
16Elfogadva5/561ms7480 KiB
17Elfogadva5/5542ms7492 KiB
18Elfogadva5/58ms5976 KiB
19Elfogadva5/59ms6024 KiB
20Elfogadva5/512ms7096 KiB
21Elfogadva5/512ms7136 KiB
22Elfogadva5/56ms5900 KiB