243742026-02-10 17:42:02algoproÚtépítéscpp17Elfogadva 100/10093ms2048 KiB
// UUID: 588e08ce-1ccc-447d-a87f-4eee63986f67
#include <bits/stdc++.h>
using namespace std;

vector<int> vis, par;
vector<vector<int>> gr;
int tim = 1;

bool dfs(int csucs) {
	vis[csucs] = tim;
	for (int i = 0; i < gr[csucs].size(); i++) {
		int x = gr[csucs][i];
		if (par[x] == -1 || (vis[par[x]] != tim && dfs(par[x]))) {
			par[x] = csucs;
			return true;
		}
	}
	return false;
}

int main() {
	int n, m;
	cin >> n >> m;
	vis.resize(((n + 2) / 2) * (m + 1) + 10);
	gr.resize(((n + 2) / 2) * (m + 1) + 10);
	par.resize(((n + 1) / 2) * (m + 1) + 10, -1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			if (c == '/') {
				if (i % 2)	gr[(i + 1) / 2 * (m + 1) + j].push_back(i / 2 * (m + 1) + j + 1);
				else gr[i / 2 * (m + 1) + j + 1].push_back(i / 2 * (m + 1) + j);
			}
			else if (c == '\\') {
				if (i % 2)	gr[(i + 1) / 2 * (m + 1) + j + 1].push_back(i / 2 * (m + 1) + j);
				else gr[i / 2 * (m + 1) + j].push_back(i / 2 * (m + 1) + j + 1);
			}
		}
	}
	vector<int> ind(((n + 2) / 2) * (m + 1));
	for (int i = 0; i < ind.size(); i++) ind[i] = i;
	random_device rd;
	mt19937 g(rd());
	shuffle(ind.begin(), ind.end(), g);
	int ans = 0;
	for (int i = 0; i < ind.size(); i++) {
		if (dfs(ind[i])) ans++;
		tim++;
	}
	cout << ans << '\n';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i % 2) {
				if (par[i / 2 * (m + 1) + j + 1] == (i + 1) / 2 * (m + 1) + j) cout << '/';
				else if (par[i / 2 * (m + 1) + j] == (i + 1) / 2 * (m + 1) + j + 1) cout << '\\';
				else cout << '.';
			}
			else {
				if (par[i / 2 * (m + 1) + j] == i / 2 * (m + 1) + j + 1) cout << '/';
				else if (par[i / 2 * (m + 1) + j + 1] == i / 2 * (m + 1) + j) cout << '\\';
				else cout << '.';
			}
		}
		cout << '\n';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/08ms1588 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms508 KiB
7Elfogadva5/51ms316 KiB
8Elfogadva5/51ms316 KiB
9Elfogadva5/51ms332 KiB
10Elfogadva5/51ms316 KiB
11Elfogadva5/52ms500 KiB
12Elfogadva5/51ms488 KiB
13Elfogadva5/51ms460 KiB
14Elfogadva5/52ms564 KiB
15Elfogadva5/53ms564 KiB
16Elfogadva5/59ms2048 KiB
17Elfogadva5/58ms1684 KiB
18Elfogadva5/593ms1564 KiB
19Elfogadva5/58ms1332 KiB
20Elfogadva5/510ms1588 KiB
21Elfogadva5/59ms1780 KiB
22Elfogadva5/57ms1276 KiB