#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> kuhn(vector<vector<int>>& g, int n, int m) {
vector<int> a(n), b(m, -1);
auto dfs = [&](auto self, int i) {
if (a[i]) {
return 0;
}
a[i] = 1;
for (int j : g[i]) {
if (b[j] == -1 || self(self, b[j])) {
b[j] = i;
return 1;
}
}
return 0;
};
for (int i = 0; i < n; i++) {
fill(a.begin(), a.end(), 0);
dfs(dfs, i);
}
return b;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin>>N>>M;
vector<vector<int>>g((N+1)*(M+1));
auto C=[&](int i, int j){
return i*(M+1)+j;
};
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
char c;
cin>>c;
if(c=='/'){
if(i%2==0){
g[C(i,j+1)].push_back(C(i+1,j));
}
else{
g[C(i+1,j)].push_back(C(i,j+1));
}
}
if(c=='\\'){
if(i%2==0){
g[C(i,j)].push_back(C(i+1,j+1));
}
else{
g[C(i+1,j+1)].push_back(C(i,j));
}
}
}
}
vector<vector<int>>a((N+2)/2*(M+1)),b((N+1)/2*(M+1));
for(int i=0;i<N+1;i++){
for(int j=0;j<M+1;j++){
for(int o:g[C(i,j)]){
int k=o/(M+1),l=o%(M+1);
if(i%2==0){
a[C(i/2,j)].push_back(C(k/2,l));
}
else {
b[C(i/2,j)].push_back(C(k/2,l));
}
}
}
}
auto x=kuhn(a,a.size(),b.size());
cout<<b.size()-count(x.begin(),x.end(),-1)<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 38/100 | ||||||
1 | Hibás válasz | 0/0 | 3ms | 2016 KiB | |||
2 | Hibás válasz | 0/0 | 131ms | 8772 KiB | |||
3 | Részben helyes | 2/5 | 3ms | 2244 KiB | |||
4 | Részben helyes | 2/5 | 3ms | 2472 KiB | |||
5 | Részben helyes | 2/5 | 3ms | 2684 KiB | |||
6 | Részben helyes | 2/5 | 3ms | 3152 KiB | |||
7 | Részben helyes | 2/5 | 3ms | 3104 KiB | |||
8 | Részben helyes | 2/5 | 3ms | 3220 KiB | |||
9 | Részben helyes | 2/5 | 3ms | 3212 KiB | |||
10 | Részben helyes | 2/5 | 3ms | 3268 KiB | |||
11 | Részben helyes | 2/5 | 3ms | 3840 KiB | |||
12 | Részben helyes | 2/5 | 3ms | 3972 KiB | |||
13 | Részben helyes | 2/5 | 3ms | 4020 KiB | |||
14 | Részben helyes | 2/5 | 12ms | 4628 KiB | |||
15 | Részben helyes | 2/5 | 13ms | 5284 KiB | |||
16 | Részben helyes | 2/5 | 145ms | 9308 KiB | |||
17 | Részben helyes | 2/5 | 131ms | 9264 KiB | |||
18 | Időlimit túllépés | 0/5 | 878ms | 6284 KiB | |||
19 | Részben helyes | 2/5 | 135ms | 9800 KiB | |||
20 | Részben helyes | 2/5 | 136ms | 11072 KiB | |||
21 | Részben helyes | 2/5 | 133ms | 11064 KiB | |||
22 | Részben helyes | 2/5 | 584ms | 10172 KiB |