13112022-05-07 17:07:56FulopMateÚtépítéscpp14Elfogadva 100/100541ms7524 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/03ms3832 KiB
2Elfogadva0/08ms6556 KiB
3Elfogadva5/53ms3852 KiB
4Elfogadva5/52ms3936 KiB
5Elfogadva5/53ms3940 KiB
6Elfogadva5/53ms4020 KiB
7Elfogadva5/53ms3952 KiB
8Elfogadva5/53ms4012 KiB
9Elfogadva5/52ms4020 KiB
10Elfogadva5/52ms4024 KiB
11Elfogadva5/53ms4108 KiB
12Elfogadva5/53ms4104 KiB
13Elfogadva5/53ms4120 KiB
14Elfogadva5/53ms4276 KiB
15Elfogadva5/54ms4808 KiB
16Elfogadva5/559ms7432 KiB
17Elfogadva5/5541ms7524 KiB
18Elfogadva5/57ms5984 KiB
19Elfogadva5/59ms6116 KiB
20Elfogadva5/510ms7092 KiB
21Elfogadva5/510ms7132 KiB
22Elfogadva5/57ms6032 KiB