240202026-02-03 18:01:09CzDaniÚtépítéscpp17Elfogadva 100/100155ms3064 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define pii pair<int ,int>
#define fi first
#define se second

int n, m, cnt = 0;
vector<vector<int>> vis(203, vector<int>(203));
vector<vector<pii>> match(203, vector<pii>(203, {-1, -1}));
vector<vector<vector<pii>>> adj(203, vector<vector<pii>>(203));

bool dfs(int x, int y) {
	if (vis[x][y]==cnt)return false;
	vis[x][y]=cnt;
	for (pii u : adj[x][y]) {
		if (make_pair(-1, -1)==match[u.fi][u.se]||dfs(match[u.fi][u.se].fi, match[u.fi][u.se].se)) {
			match[u.fi][u.se] = {x, y};
			return true;
		}
	}
	return false;
}

int main() {
	std::random_device rd;
    std::mt19937 g(rd());
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++) {
			char c = s[j-1];
			if (c=='\\') {
				if (i%2) {
					adj[i][j].push_back({i+1, j+1});
				} else {
					adj[i+1][j+1].push_back({i, j});
				}
			}
			if (c=='/') {
				if (i%2) {
					adj[i][j+1].push_back({i+1, j});
				} else {
					adj[i+1][j].push_back({i, j+1});
				}
			}
		}
	}
	vector<vector<char>> ansv(n+1, vector<char>(m+1, '.'));
	int ans = 0;
	vector<pii> vp;
	for (int i = 1; i <= n+1; i+=2) {
		for (int j = 1; j <= m+1; j++) {
			vp.push_back({i,j});
			// cnt++;
			// ans += dfs(i, j);
		}
	}
	shuffle(vp.begin(), vp.end(), g);
	for (auto p : vp) {
		cnt++;
		ans += dfs(p.fi, p.se);
	}
	for (int i = 2; i <= n+1; i+=2) {
		for (int j = 1; j <= m+1; j++) {
			if (match[i][j]!=make_pair(-1, -1)) {
				if (match[i][j]==make_pair(i+1, j+1)) {
					ansv[i][j]='\\';
				}
				if (match[i][j]==make_pair(i-1, j+1)) {
					ansv[i-1][j]='/';
				}
				if (match[i][j]==make_pair(i+1, j-1)) {
					ansv[i][j-1]='/';
				}
				if (match[i][j]==make_pair(i-1, j-1)) {
					ansv[i-1][j-1]='\\';
				}
			}
		}
	}
	cout << ans << '\n';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << ansv[i][j];
		}
		cout<<'\n';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/02ms2028 KiB
2Elfogadva0/08ms2736 KiB
3Elfogadva5/53ms1844 KiB
4Elfogadva5/53ms1844 KiB
5Elfogadva5/53ms1844 KiB
6Elfogadva5/52ms1844 KiB
7Elfogadva5/52ms1844 KiB
8Elfogadva5/53ms1844 KiB
9Elfogadva5/53ms1844 KiB
10Elfogadva5/53ms1844 KiB
11Elfogadva5/53ms1844 KiB
12Elfogadva5/53ms1844 KiB
13Elfogadva5/53ms1724 KiB
14Elfogadva5/53ms1820 KiB
15Elfogadva5/54ms2100 KiB
16Elfogadva5/58ms2560 KiB
17Elfogadva5/58ms2740 KiB
18Elfogadva5/5155ms2828 KiB
19Elfogadva5/58ms2612 KiB
20Elfogadva5/510ms3064 KiB
21Elfogadva5/510ms2868 KiB
22Elfogadva5/58ms2580 KiB