240242026-02-03 18:04:47algoproÚtépítéscpp17Time limit exceeded 90/100892ms2868 KiB
// UUID: 0aa35a37-2611-4e53-ada7-46e12fb3d181
#include <bits/stdc++.h>
using namespace std;

int n, m;

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));
			}
		}
	}

	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";
}
SubtaskSumTestVerdictTimeMemory
base90/100
1Accepted0/01ms316 KiB
2Accepted0/0122ms2612 KiB
3Accepted5/51ms316 KiB
4Accepted5/51ms316 KiB
5Accepted5/51ms316 KiB
6Accepted5/51ms316 KiB
7Accepted5/51ms316 KiB
8Accepted5/51ms332 KiB
9Accepted5/51ms316 KiB
10Accepted5/51ms316 KiB
11Accepted5/52ms564 KiB
12Accepted5/52ms316 KiB
13Accepted5/52ms316 KiB
14Accepted5/510ms756 KiB
15Accepted5/513ms1036 KiB
16Accepted5/5145ms2356 KiB
17Accepted5/5128ms2356 KiB
18Time limit exceeded0/5892ms2100 KiB
19Accepted5/5136ms2356 KiB
20Accepted5/5134ms2864 KiB
21Accepted5/5131ms2832 KiB
22Time limit exceeded0/5808ms2868 KiB