/* -*- coding: utf-8 -*- * * 861.cc: No.861 ケーキカット - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int N = 5; const int NN = N * N; const int M = (N - 1) * 4; const int K = NN - M; const int KBITS = 1 << K; const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; struct UFT { int links[NN], ranks[NN], sizes[NN]; UFT() {} void init(int n) { for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1; } int root(int i) { int i0 = i; while (links[i0] != i0) i0 = links[i0]; return (links[i] = i0); } int rank(int i) { return ranks[root(i)]; } int size(int i) { return sizes[root(i)]; } bool same(int i, int j) { return root(i) == root(j); } int merge(int i0, int i1) { int r0 = root(i0), r1 = root(i1), mr; if (r0 == r1) return r0; if (ranks[r0] == ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; ranks[r0]++; mr = r0; } else if (ranks[r0] > ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; mr = r0; } else { links[r0] = r1; sizes[r1] += sizes[r0]; mr = r1; } return mr; } }; /* global variables */ int cs[N][N]; int rxs[M], rys[M], kxs[K], kys[K]; ll rsums[M + 1], ksums[KBITS]; bool bs[N][N]; UFT uft; /* subroutines */ inline int xy2p(int x, int y) { return y * N + x; } inline void p2xy(int p, int &x, int &y) { x = p % N, y = p / N; } /* main */ int main() { ll csum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &cs[i][j]), csum += cs[i][j]; int m = 0; for (int x = 0; x < N - 1; x++) rxs[m] = x, rys[m] = 0, m++; for (int y = 0; y < N - 1; y++) rxs[m] = N - 1, rys[m] = y, m++; for (int x = N - 1; x > 0; x--) rxs[m] = x, rys[m] = N - 1, m++; for (int y = N - 1; y > 0; y--) rxs[m] = 0, rys[m] = y, m++; //printf("m=%d\n", m); for (int i = 0; i < M; i++) rsums[i + 1] = rsums[i] + cs[rys[i]][rxs[i]]; for (int k = 0, y = 1; y < N - 1; y++) for (int x = 1; x < N - 1; x++, k++) kxs[k] = x, kys[k] = y; for (int bits = 1, msb = 1, bi = 0; bits < KBITS; bits++) { if ((msb << 1) <= bits) msb <<= 1, bi++; ksums[bits] = ksums[bits ^ msb] + cs[kys[bi]][kxs[bi]]; } ll mind = LINF; for (int i0 = 0; i0 < M; i0++) for (int i1 = i0 + 1; i1 <= M; i1++) { memset(bs, false, sizeof(bs)); for (int i = i0; i < i1; i++) bs[rys[i]][rxs[i]] = true; for (int bits = 0; bits < KBITS; bits++) { ll s0 = rsums[i1] - rsums[i0] + ksums[bits], s1 = csum - s0; ll d = abs(s1 - s0); if (mind > d) { for (int i = 0, bi = 1; i < K; i++, bi <<= 1) if (bits & bi) bs[kys[i]][kxs[i]] = true; uft.init(NN); int sn = NN; for (int y = 0, p = 0; y < N; y++) for (int x = 0; x < N; x++, p++) { if (x + 1 < N && bs[y][x] == bs[y][x + 1] && ! uft.same(p, p + 1)) { uft.merge(p, p + 1); sn--; } if (y + 1 < N && bs[y][x] == bs[y + 1][x] && ! uft.same(p, p + N)) { uft.merge(p, p + N); sn--; } } if (sn == 2) mind = d; } } } printf("%lld\n", mind); return 0; }