241352026-02-04 17:49:43algoproÚtépítéscpp17Időlimit túllépés 95/100899ms2868 KiB
// UUID: 406bcde8-d914-476d-b11f-98ea41af57cb
#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() {
	std::random_device rd;
    std::mt19937 my_random(rd());
	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){
		shuffle(x.begin(), x.end(), my_random);
	}

	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/01ms512 KiB
2Elfogadva0/010ms2508 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms560 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva5/51ms316 KiB
8Elfogadva5/51ms316 KiB
9Elfogadva5/51ms316 KiB
10Elfogadva5/51ms316 KiB
11Elfogadva5/52ms464 KiB
12Elfogadva5/51ms316 KiB
13Elfogadva5/52ms580 KiB
14Elfogadva5/52ms724 KiB
15Elfogadva5/54ms820 KiB
16Elfogadva5/517ms2432 KiB
17Elfogadva5/58ms2360 KiB
18Időlimit túllépés0/5899ms2168 KiB
19Elfogadva5/519ms2292 KiB
20Elfogadva5/513ms2696 KiB
21Elfogadva5/512ms2868 KiB
22Elfogadva5/5771ms2576 KiB