240382026-02-03 18:18:28algoproÚtépítéscpp17Hibás válasz 0/100228ms3124 KiB
// UUID: bfacff29-1e1a-4ba1-af1f-2a7050d73f75
#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);
		cout<<c<<"\n";
	}

	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
base0/100
1Hibás válasz0/01ms316 KiB
2Hibás válasz0/0134ms2868 KiB
3Hibás válasz0/51ms316 KiB
4Hibás válasz0/51ms316 KiB
5Hibás válasz0/51ms316 KiB
6Hibás válasz0/51ms316 KiB
7Hibás válasz0/51ms316 KiB
8Hibás válasz0/51ms316 KiB
9Hibás válasz0/51ms316 KiB
10Hibás válasz0/51ms316 KiB
11Hibás válasz0/52ms564 KiB
12Hibás válasz0/52ms564 KiB
13Hibás válasz0/52ms784 KiB
14Hibás válasz0/513ms820 KiB
15Hibás válasz0/514ms868 KiB
16Hibás válasz0/5130ms2784 KiB
17Hibás válasz0/5130ms3064 KiB
18Hibás válasz0/5228ms2704 KiB
19Hibás válasz0/5129ms2612 KiB
20Hibás válasz0/5138ms3124 KiB
21Hibás válasz0/5133ms3076 KiB
22Hibás válasz0/5128ms2356 KiB