//#define _GLIBCXX_DEBUG #include #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater >; const int INF = 0xccccccc; const ll LINF = 922337203685477580LL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} struct UnionFind { vector par; // 親を指すvector,-par[親]は木のサイズ UnionFind(int n):par(n, -1) {} // uniteで親を埋め込んでいく必要あり inline void init() {fill(par.begin(), par.end(), -1);} int root(int x) { // 親をたどる&データの整理 if(par[x] < 0) return x; return par[x] = root(par[x]); } bool unite(int x, int y) { // データの結合 x = root(x); y = root(y); if(x == y) return false; if(par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } bool same(int x, int y) {return root(x) == root(y);} // 所属判定 int size(int x) {return -par[root(x)];} // 木のサイズ }; const int N = 5; const int X = 25; const bitset around("1111110001100011000111111"); //head bitset simple[X]; bitset around_[16]; bitset cap[9]; int c[N][N]; ll ans = LINF; bitset now; UnionFind uft(X); int di[] = {0, 1, 0, -1}; int dj[] = {1, 0, -1, 0}; inline bool able(int i, int j) {return i >= 0 and j >= 0 and i < 5 and j < 5;} int main() { ios::sync_with_stdio(false); cin.tie(0); rep(i, 25) { simple[i] = 1<> c[i][j]; rep(i, 16) rep(j, i+!i) { bitset oo = around_[i]^around_[j]; rep(qwer, 2) { rep(i, 1<<9) { now = oo; rep(j, 9) if(i>>j&1) now |= cap[j]; int w = -1, b = -1; rep(i, 25) { if(now.test(i)) b = i; else w = i; } if(w == -1 or b == -1) continue; ll cnt = 0; uft.init(); bitset check(0); queue

q; q.emplace(w/5, w%5); check.set(w); while(!q.empty()) { int i, j; tie(i, j) = q.front(); q.pop(); cnt += c[i][j]; rep(k, 4) { int ni = i+di[k]; int nj = j+dj[k]; if(able(ni, nj) and !check.test(ni*5+nj) and !now.test(ni*5+nj)) { check.set(ni*5+nj); q.emplace(ni, nj); uft.unite(w, ni*5+nj); } } } q.emplace(b/5, b%5); check.set(b); while(!q.empty()) { int i, j; tie(i, j) = q.front(); q.pop(); cnt -= c[i][j]; rep(k, 4) { int ni = i+di[k]; int nj = j+dj[k]; if(able(ni, nj) and !check.test(ni*5+nj) and now.test(ni*5+nj)) { check.set(ni*5+nj); q.emplace(ni, nj); uft.unite(b, ni*5+nj); } } } if(uft.size(b) + uft.size(w) == 25) chmin(ans, abs(cnt)); } oo ^= around; } } cout << ans << endl; }