#include #define LOCAL using std::to_string; auto to_string(std::string s) -> std::string { return '"' + s + '"'; } auto to_string(char c) -> std::string { return "'" + std::string{c} + "'"; } auto to_string(const char* s) -> std::string { return to_string((std::string) s); } auto to_string(bool b) -> std::string { return (b ? "true" : "false"); } template auto to_string(std::pair p) -> std::string { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template auto to_string(std::bitset bs) -> std::string { std::string res{}; for (size_t i = 0; i < N; i++) res.insert(res.begin(), bs.test(i) ? '1' : '0'); return res; } template auto to_string(T v) -> std::string { bool flg = false; std::string res = "{"; for (auto const&x : v) { if (flg) res += ", "; else flg = true; res += to_string(x); } res += "}"; return res; } void debug_out() { std::cerr << std::endl; } template void debug_out(Head H, Tail... T) { std::cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template class fixed_point : T { public: explicit constexpr fixed_point (T&& t) noexcept : T(std::forward(t)) {} template constexpr decltype(auto) operator()(Args&&... args) const {return T::operator()(*this, std::forward(args)...);} }; template static inline constexpr decltype(auto) fix (T&& t) noexcept { return fixed_point{std::forward(t)}; } int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); constexpr int n = 5, N = 25, bsm = 1 << N; auto a = std::vector>(n, std::vector(n)); for (auto& v : a) for (auto& x : v) std::cin >> x; int di[4] = {-1, +1, 0, 0}; int dj[4] = {0, 0, -1, +1}; auto encode = [&] (int i, int j) { assert(0 <= i && i < n); assert(0 <= j && j < n); return i * n + j; }; auto decode = [&] (int pos) { assert(0 <= pos && pos < N); return std::pair{pos / n, pos % n}; }; // Access the j-th bit. auto at = [](unsigned x, size_t j) -> bool { return (x >> j) & 1; }; auto check = [&] (int bs) -> bool { int ckd = 0; auto dfs = fix ([&](auto dfs, int crr) -> void { assert(0 <= crr && crr < N); ckd |= 1 << crr; auto [cri, crj] = decode(crr); for (int k = 0; k < 4; k++) { int nxi = cri + di[k]; int nxj = crj + dj[k]; if (nxi < 0 || n <= nxi || nxj < 0 || n <= nxj) { continue; } auto nxt = encode(nxi, nxj); if (at(ckd, nxt) || !at(bs, nxt)) { continue; } dfs(nxt); } }); if (bs == 0) return true; for (int i = 0; i < N; i++) { if (at(bs, i)) { dfs(i); break; } } return bs == ckd; }; constexpr long long inf = 1LL << 60; auto acm = [&] (int bs) -> long long{ long long ret = 0; for (int pos = 0; pos < N; pos++) { auto [i, j] = decode(pos); if (at(bs, pos)) ret += a.at(i).at(j); } return ret; }; long long sum = acm(bsm - 1); auto cal = [&] (int bs) -> long long { int cs = (bsm - 1) ^ bs; assert(!(bs & cs)); assert((bs | cs) == (bsm - 1)); if (!check(bs) || !check(cs)) return inf; if (bs > cs) return inf; auto ret = std::abs(sum - 2 * acm(bs)); return ret; }; long long ret = inf; for (int bs = 1; bs < bsm - 1; bs++) { ret = std::min(ret, cal(bs)); } std::cout << ret << std::endl; return 0; }