240392026-02-03 18:19:23algoproÚtépítéscpp17Elfogadva 100/100221ms3056 KiB
// UUID: 690c2e0c-698c-40ee-ac9e-7a81fe71a0f7
#include <bits/stdc++.h>
#include <random>
using namespace std;

int n, m;
mt19937 rnd;

int ti(int i, int j) {return i * (m + 1) + j;}
array<int, 2> tc(int c) {return {c / (m + 1), c % (m + 1)};}

bool scc(int c, vector<int> &p, vector<int> &vis, vector<vector<int>> &e) {
	vis[c] = true;
	for (int d : e[c]) {
		if (p[d] == -1 || (!vis[p[d]] && scc(p[d], p, vis, e))) {
			p[d] = c;
			return true;
		}
	}

	return false;
}


int main() {
	cin >> n >> m;
	vector<int> p((n + 1) * (m + 1), -1), vis((n + 1) * (m + 1));
	vector<vector<int>> e((n + 1) * (m + 1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			if (c == '\\') {
				e[ti(i, j)].push_back(ti(i + 1, j + 1));
				e[ti(i + 1, j + 1)].push_back(ti(i, j));
			}

			if (c == '/') {
				e[ti(i + 1, j)].push_back(ti(i, j + 1));
				e[ti(i, j + 1)].push_back(ti(i + 1, j));
			}
		}
	}

	vector<int> ord;
	for (int i = 0; i < n + 1; i += 2) {
		for (int j = 0; j < m + 1; j++) {
			ord.push_back(ti(i, j));
		}
	}

	shuffle(ord.begin(), ord.end(), rnd);
	for (int c : ord) {
		vis.assign((n + 1) * (m + 1), false);
		scc(c, p, vis, e);
	}

	vector<string> ans(n, string(m, '.'));
	int cnt = 0;
	for (int i = 1; i < n + 1; i += 2) {
		for (int j = 0; j < m + 1; j++) {
			if (p[ti(i, j)] == -1) continue;
			cnt++;
			auto x = tc(p[ti(i, j)]);
			if (x == array<int, 2> {i - 1, j - 1}) ans[i - 1][j - 1] = '\\';
			if (x == array<int, 2> {i + 1, j + 1}) ans[i][j] = '\\';
			if (x == array<int, 2> {i - 1, j + 1}) ans[i - 1][j] = '/';
			if (x == array<int, 2> {i + 1, j - 1}) ans[i][j - 1] = '/';
		}
	}

	cout << cnt << "\n";
	for (string line : ans) cout << line << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/0125ms2868 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva5/51ms316 KiB
8Elfogadva5/51ms508 KiB
9Elfogadva5/51ms420 KiB
10Elfogadva5/51ms316 KiB
11Elfogadva5/52ms564 KiB
12Elfogadva5/52ms564 KiB
13Elfogadva5/52ms576 KiB
14Elfogadva5/512ms820 KiB
15Elfogadva5/513ms1080 KiB
16Elfogadva5/5130ms2868 KiB
17Elfogadva5/5130ms3040 KiB
18Elfogadva5/5221ms2532 KiB
19Elfogadva5/5130ms2356 KiB
20Elfogadva5/5137ms2864 KiB
21Elfogadva5/5131ms3056 KiB
22Elfogadva5/5126ms2356 KiB