240162026-02-03 17:54:41algoproÚtépítéscpp17Időlimit túllépés 95/100898ms2612 KiB
// UUID: 80845514-f25b-4298-90b3-e2070fa05594
#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() {
	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;
	for (int i = 1; i <= n+1; i+=2) {
		for (int j = 1; j <= m+1; j++) {
			cnt++;
			ans += dfs(i, j);
		}
	}
	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
base95/100
1Elfogadva0/02ms2028 KiB
2Elfogadva0/08ms2356 KiB
3Elfogadva5/53ms1844 KiB
4Elfogadva5/53ms1844 KiB
5Elfogadva5/53ms1844 KiB
6Elfogadva5/52ms1844 KiB
7Elfogadva5/52ms1844 KiB
8Elfogadva5/53ms1844 KiB
9Elfogadva5/53ms1764 KiB
10Elfogadva5/52ms1884 KiB
11Elfogadva5/53ms1844 KiB
12Elfogadva5/53ms1848 KiB
13Elfogadva5/53ms1844 KiB
14Elfogadva5/53ms1844 KiB
15Elfogadva5/54ms1844 KiB
16Elfogadva5/532ms2100 KiB
17Elfogadva5/56ms2100 KiB
18Időlimit túllépés0/5898ms2356 KiB
19Elfogadva5/517ms2100 KiB
20Elfogadva5/59ms2612 KiB
21Elfogadva5/58ms2612 KiB
22Elfogadva5/5788ms2612 KiB