241342026-02-04 17:47:30algoproÚtépítéscpp17Időlimit túllépés 95/100899ms2844 KiB
// UUID: 0e33f5ca-ed75-4c61-a4f9-18e7176306ff
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

vector<vector<int>> csucsok;
vector<bool> bejart;
vector<int> par;

bool dfs(int akt){
	bejart[akt] = true;

	for(int x : csucsok[akt]){
		if(par[x] == -1){
			par[x] = akt;
			bejart[akt] = 0;
			return true;
		} else{
			if(bejart[par[x]]) continue;

			if(dfs(par[x])){
				par[x] = akt;
				bejart[akt] = false;
				return true;
			}
		}
	}

	bejart[akt] = false;

	return false;
}

int main() {
	int n, m;
	cin >> n >> m;

	int ossz = (n+1)*(m+1);

	csucsok.assign(ossz, vector<int>());

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;

		for(int j = 0; j < m; j++){
			int akt = i*(m+1) + j;

			if(s[j] == '/'){
				csucsok[akt + 1].push_back(akt + m + 1);
				csucsok[akt + m + 1].push_back(akt + 1);
			} else if(s[j] == '\\'){
				csucsok[akt].push_back(akt + m + 2);
				csucsok[akt + m + 2].push_back(akt);
			}
		}
	}

	for(auto &x : csucsok){
		random_shuffle(x.begin(), x.end());
	}

	par.assign(ossz, -1);
	bejart.assign(ossz, 0);


	int ans = 0;
	for(int i = 0; i < ossz; i++){
		if((i / (m+1)) % 2 == 1) continue;

		int a = dfs(i);
		ans += a;
	}

	cout << ans << "\n";

	vector<vector<int>> valasz(n+1, vector<int>(m+1, 0));

	for(int i = 1; i < n+1; i+= 2){
		for(int j = 0; j < m+1; j++){
			if(par[i*(m+1) + j] == -1) continue;

			int akt = i*(m+1) + j;
			int kovi = par[akt];

			if(kovi + m+2 == akt){
				valasz[i - 1][j - 1] = 1;
			} else if(kovi + m == akt){
				valasz[i - 1][j] = 2;
			} else if(akt + m == kovi){
				valasz[i][j - 1] = 2;
			} else if(akt + m+2 == kovi){
				valasz[i][j] = 1;
			} else{
				assert(0 == 1);
			}
		}
	}

	string s = ".\\/";

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << s[valasz[i][j]];
		}
		cout << "\n";
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base95/100
1Elfogadva0/01ms500 KiB
2Elfogadva0/09ms2612 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva5/51ms316 KiB
8Elfogadva5/51ms316 KiB
9Elfogadva5/51ms316 KiB
10Elfogadva5/51ms316 KiB
11Elfogadva5/52ms324 KiB
12Elfogadva5/52ms316 KiB
13Elfogadva5/52ms532 KiB
14Elfogadva5/52ms756 KiB
15Elfogadva5/54ms820 KiB
16Elfogadva5/517ms2408 KiB
17Elfogadva5/58ms2160 KiB
18Időlimit túllépés0/5899ms2084 KiB
19Elfogadva5/520ms2164 KiB
20Elfogadva5/513ms2844 KiB
21Elfogadva5/512ms2776 KiB
22Elfogadva5/5800ms2660 KiB