이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
class BipartiteMatcher{
int n, m;
vector<int> l;
vector<int> r;
vector<vector<int> > graph;
vector<bool> viz;
bool pairup(int nod){
if(viz[nod] == true){
return false;
}
viz[nod] = true;
for(auto it:graph[nod]){
if(r[it] == -1){
l[nod] = it;
r[it] = nod;
return true;
}
}
for(auto it:graph[nod]){
if(pairup(r[it])){
l[nod] = it;
r[it] = nod;
return true;
}
}
return false;
}
public:
BipartiteMatcher(int n, int m) {
this->n = n;
this->m = m;
this->l = vector<int>(n, -1);
this->r = vector<int>(m, -1);
this->graph = vector<vector<int> >(n, vector<int>());
this->viz = vector<bool>(n, false);
}
void add_edge(int x, int y){
graph[x].push_back(y);
}
int solve(){
bool ok = true;
while(ok){
ok = false;
for(int i = 0;i < n;i++){
viz[i] = false;
}
for(int i = 0;i < n;i++){
if(l[i] == -1 && pairup(i)){
ok = true;
}
}
}
int cuplaj = 0;
for(int i = 0;i < n;i++){
cuplaj += (l[i] != -1);
}
return cuplaj;
}
};
int main(){
int n, m;
cin >> n >> m;
vector<string> v(n,"");
vector<vector<int> > horizontal_group(n, vector<int>(m, -1));
vector<vector<int> > vertical_group(n, vector<int>(m, -1));
for(int i = 0;i < n;i++){
cin >> v[i];
}
int cnt_horizontal = 0;
int cnt_vertical = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(j + 2 < m && v[i][j] == 'R' && v[i][j + 1] == 'G' && v[i][j + 2] == 'W'){
horizontal_group[i][j] = cnt_horizontal;
horizontal_group[i][j + 1] = cnt_horizontal;
horizontal_group[i][j + 2] = cnt_horizontal;
cnt_horizontal++;
}
if(i + 2 < n && v[i][j] == 'R' && v[i + 1][j] == 'G' && v[i + 2][j] == 'W'){
vertical_group[i][j] = cnt_vertical;
vertical_group[i + 1][j] = cnt_vertical;
vertical_group[i + 2][j] = cnt_vertical;
cnt_vertical++;
}
}
}
BipartiteMatcher matcher(cnt_horizontal, cnt_vertical);
for(int i = 0;i < n;i++){
for(int j = 0; j < m;j++){
if(vertical_group[i][j] != -1 && horizontal_group[i][j] != -1){
matcher.add_edge(vertical_group[i][j], horizontal_group[i][j]);
}
}
}
printf("%d", cnt_horizontal + cnt_vertical - matcher.solve());
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |