240342026-02-03 18:09:36algoproÚtépítéscpp17Időlimit túllépés 90/100883ms2872 KiB
// UUID: f096115f-2795-42ca-b3c3-622b774420f0
#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;
	shuffle(e[c].begin(), e[c].end(), rnd);
	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));
			}
		}
	}

	for (int i = 0; i < n + 1; i += 2) {
		for (int j = 0; j < m + 1; j++) {
			vis.assign((n + 1) * (m + 1), false);
			scc(ti(i, j), 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
base90/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/0119ms2612 KiB
3Elfogadva5/51ms316 KiB
4Elfogadva5/51ms316 KiB
5Elfogadva5/51ms316 KiB
6Elfogadva5/51ms316 KiB
7Elfogadva5/51ms316 KiB
8Elfogadva5/51ms316 KiB
9Elfogadva5/51ms508 KiB
10Elfogadva5/51ms392 KiB
11Elfogadva5/52ms564 KiB
12Elfogadva5/52ms460 KiB
13Elfogadva5/52ms564 KiB
14Elfogadva5/510ms564 KiB
15Elfogadva5/513ms1028 KiB
16Elfogadva5/5141ms2308 KiB
17Elfogadva5/5125ms2356 KiB
18Időlimit túllépés0/5883ms2100 KiB
19Elfogadva5/5143ms2356 KiB
20Elfogadva5/5131ms2868 KiB
21Elfogadva5/5130ms2872 KiB
22Időlimit túllépés0/5875ms2612 KiB