10003 2024. 03. 23 21:01:50 111 Útépítés cpp17 Elfogadva 100/100 246ms 10020 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> kuhn(vector<vector<int>>& g, int n, int m) {
	vector<int> a(n), b(m, -1);
	auto dfs = [&](auto self, int i) {
		if (a[i]) {
			return 0;
		}
		a[i] = 1;
		for (int j : g[i]) {
			if (b[j] == -1 || self(self, b[j])) {
				b[j] = i;
				return 1;
			}
		}
		return 0;
	};
	vector<int> tmp(n);
	for (int i = 0; i < n; i++) {
		for (int j : g[i]) {
			if (b[j] == -1) {
				b[j] = i;
				tmp[i] = 1;
				break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (tmp[i]) {
			continue;
		}
		fill(a.begin(), a.end(), 0);
		dfs(dfs, i);
	}
	return b;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>g((N+1)*(M+1));
	auto C=[&](int i, int j){
		return i*(M+1)+j;
	};
	auto D=[&](int i, int j){
		return i*(M+2)/2+j;
	};
	auto E=[&](int i, int j){
		return i*(M+1)/2+j;
	};
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			char c;
			cin>>c;
			if(c=='/'){
				if(i%2==0){
					g[C(i,j+1)].push_back(C(i+1,j));
				}
				else{
					g[C(i+1,j)].push_back(C(i,j+1));
				}
			}
			if(c=='\\'){
				if(i%2==0){
					g[C(i,j)].push_back(C(i+1,j+1));
				}
				else{
					g[C(i+1,j+1)].push_back(C(i,j));
				}
			}
		}
	}
	vector<vector<int>>a((N+2)/2*(M+2)/2),b((N+2)/2*(M+1)/2);
	for(int i=0;i<N+1;i++){
		for(int j=0;j<M+1;j++){
			for(int o:g[C(i,j)]){
				int k=o/(M+1),l=o%(M+1);
				if(i%2==0){
					if(j%2==0){
						a[D(i/2,j/2)].push_back(E(k/2,l/2));
					}
					else{
						b[E(i/2,j/2)].push_back(D(k/2,l/2));
					}
				}
			}
		}
	}
	int aa=(N+1)/2*(M+1)/2;
	int bb=(N+1)/2*(M+2)/2;
	auto x=kuhn(a,a.size(),aa);
	auto y=kuhn(b,b.size(),bb);
	char ans[N][M];
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			ans[i][j]='.';
		}
	}
	int ansc=0;
	for(int i=0;i<N+1;i++){
		for(int j=0;j<M+1;j++){
			for(int o:g[C(i,j)]){
				int k=o/(M+1),l=o%(M+1);
				int cc=0;
				if(i%2==0){
					if(j%2==0&&x[E(k/2,l/2)]==D(i/2,j/2)){
						ansc++;
						cc=1;
					}
					if(j%2==1&&y[D(k/2,l/2)]==E(i/2,j/2)){
						ansc++;
						cc=1;
					}
				}
				if(cc){
					if(k==i-1&&l==j-1){
						ans[i-1][j-1]='\\';
					}
					if(k==i-1&&l==j+1){
						ans[i-1][j]='/';
					}
					if(k==i+1&&l==j+1){
						ans[i][j]='\\';
					}
					if(k==i+1&&l==j-1){
						ans[i][j-1]='/';
					}
				}
			}
		}
	}
	cout<<ansc<<'\n';
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cout<<ans[i][j];
		}
		cout<<'\n';
	}
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 34ms 7756 KiB
3 Elfogadva 5/5 3ms 2272 KiB
4 Elfogadva 5/5 3ms 2456 KiB
5 Elfogadva 5/5 3ms 2680 KiB
6 Elfogadva 5/5 3ms 3076 KiB
7 Elfogadva 5/5 3ms 2952 KiB
8 Elfogadva 5/5 3ms 3184 KiB
9 Elfogadva 5/5 3ms 3412 KiB
10 Elfogadva 5/5 3ms 3616 KiB
11 Elfogadva 5/5 3ms 3832 KiB
12 Elfogadva 5/5 3ms 3820 KiB
13 Elfogadva 5/5 3ms 4124 KiB
14 Elfogadva 5/5 4ms 4472 KiB
15 Elfogadva 5/5 6ms 5072 KiB
16 Elfogadva 5/5 43ms 8440 KiB
17 Elfogadva 5/5 41ms 9488 KiB
18 Elfogadva 5/5 61ms 9116 KiB
19 Elfogadva 5/5 48ms 8784 KiB
20 Elfogadva 5/5 26ms 10008 KiB
21 Elfogadva 5/5 27ms 10020 KiB
22 Elfogadva 5/5 246ms 9256 KiB