Submission #2025646

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<class V> struct MaxFlow { // Dinic O(V^2E)
    struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
    int MV; vector<vector<edge>> E; vector<int> itr, lev;
    MaxFlow(int n) { init(n); } MaxFlow() { }
    void init(int n){MV=n;itr=vector<int>(MV),lev = vector<int>(MV); E = vector<vector<edge>>(MV); }
    void add_edge(int x, int y, V cap, bool undir = false) {
        E[x].push_back(edge(y, (int)E[y].size(), cap));
        E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0));}
    void bfs(int cur) {rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
        while (q.size()) {int v = q.front(); q.pop();
        for (auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to);}}
    V dfs(int from,int to,V cf){if(from==to)return cf;for(; itr[from]<E[from].size(); itr[from]++) {
        edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {
        V f = dfs(e->to, to, min(cf, e->cap));if(f>0){e->cap-=f;E[e->to][e->reve].cap+=f;return f; }}
        } return 0;}
    V maxflow(int from, int to) {V fl = 0, tf;while (1) {bfs(from); if (lev[to]<0) return fl;
        rep(i,0,MV)itr[i]=0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;}}};
struct BipartiteMatching {
    int N, M; MaxFlow<int> mf;
    BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }
    void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }
    int match() { rep(a, 0, N) mf.add_edge(N + M, a, 1); rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);
        return mf.maxflow(N + M, N + M + 1); }
    // マッチング相手を返す(無いなら-1)
    int whois(int a) { for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N; return -1; }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int H, W;
string C[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> C[y];

    int N = H * W;
    BipartiteMatching bm(N, N);
    rep(y, 0, H) rep(x, 0, W) {
        if ((y + x) % 2 == 0) {
            if(x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x, y * W + x + 1);
            if(y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge(y * W + x, (y + 1) * W + x);
        }
        else {
            if (x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x + 1, y * W + x);
            if (y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge((y + 1) * W + x, y * W + x);
        }
    }

    int ans = -bm.match();
    rep(y, 0, H) rep(x, 0, W) if (C[y][x] == '.') ans++;
    cout << ans << endl;
}

Submission Info

Judge Result