Submission #2038948
Source Code Expand
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;
#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end
typedef long long ll;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
// const int C = 1e6+10;
//--------------二部マッチング--------------------
int MAX_V;
vector<int> G[100010];
int match[100010];
bool used[100010];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v) {
used[v] = true;
for (auto u : G[v]) {
int w = match[u];
if (w < 0 || (!used[w] && dfs(w))) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int bipartite_matching() {
int res = 0;
fill(match, match+100010, -1);
for (auto v = 0; v < MAX_V; ++v) {
if (match[v] < 0) {
fill(used, used+100010, false);
if (dfs(v)) {
res++;
}
}
}
return res++;
}
//---------------------------------------------------
int R, C;
string S[100];
int vertex = 0;
bool valid(int i, int j) {
return (0 <= i && i < R && 0 <= j && j < C && S[i][j] == '.');
}
int num(int i, int j) {
return i * C + j;
}
void add_edge_grid(int i, int j) {
if (!valid(i, j)) return;
int now = num(i, j);
vertex++;
if ((i+j) % 2 == 0) {
for (auto k = 0; k < 4; ++k) {
int x = i + dx[k];
int y = j + dy[k];
if (valid(x, y)) {
add_edge(now, num(x, y));
#if DEBUG == 1
// cerr << "add_edge(" << now << ", " << num(x, y) << ", 1)" << endl;
#endif
}
}
} else {
//
}
}
int main () {
cin >> R >> C;
for (auto i = 0; i < R; ++i) {
cin >> S[i];
}
MAX_V = R * C - 1;
for (auto i = 0; i < R; ++i) {
for (auto j = 0; j < C; ++j) {
add_edge_grid(i, j);
}
}
ll maxi = bipartite_matching();
#if DEBUG == 1
cerr << "vertex = " << vertex << endl;
cerr << "maxi = " << maxi << endl;
#endif
cout << vertex - maxi << endl;
}
Submission Info
Submission Time |
|
Task |
C - 広告 |
User |
kazunetakahashi |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2729 Byte |
Status |
AC |
Exec Time |
60 ms |
Memory |
3072 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample0.txt, sample1.txt, sample2.txt, sample3.txt |
All |
01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
01-00.txt |
AC |
60 ms |
3072 KB |
01-01.txt |
AC |
42 ms |
3072 KB |
01-02.txt |
AC |
58 ms |
3072 KB |
01-03.txt |
AC |
46 ms |
3072 KB |
01-04.txt |
AC |
38 ms |
3072 KB |
01-05.txt |
AC |
44 ms |
3072 KB |
01-06.txt |
AC |
40 ms |
3072 KB |
01-07.txt |
AC |
58 ms |
3072 KB |
01-08.txt |
AC |
42 ms |
3072 KB |
01-09.txt |
AC |
38 ms |
3072 KB |
01-10.txt |
AC |
39 ms |
3072 KB |
01-11.txt |
AC |
60 ms |
3072 KB |
01-12.txt |
AC |
39 ms |
3072 KB |
01-13.txt |
AC |
39 ms |
3072 KB |
01-14.txt |
AC |
48 ms |
3072 KB |
01-15.txt |
AC |
38 ms |
3072 KB |
01-16.txt |
AC |
55 ms |
3072 KB |
sample0.txt |
AC |
3 ms |
3072 KB |
sample1.txt |
AC |
3 ms |
3072 KB |
sample2.txt |
AC |
3 ms |
2944 KB |
sample3.txt |
AC |
3 ms |
3072 KB |