#include using namespace std; class DLX { protected: struct Node { size_t l, r, u, d, row, col; constexpr Node(size_t l = 0, size_t r = 0, size_t u = 0, size_t d = 0, size_t row = 0, size_t col = 0) : l(l), r(r), u(u), d(d), row(row), col(col) {} friend std::ostream &operator<<(std::ostream &os, Node const &data) { return os << data.l << ' ' << data.r << ' ' << data.u << ' ' << data.d << ' ' << data.row << ' ' << data.col; } }; std::vector data; std::vector cnt_col; bool multians; #define l_(x) data[x].l #define r_(x) data[x].r #define u_(x) data[x].u #define d_(x) data[x].d #define row_(x) data[x].row #define col_(x) data[x].col #define for_(i, start, dir) \ for (size_t start__ = (start), i = dir##_(start__); i != start__; \ i = dir##_(i)) void remove_(size_t col) { r_(l_(col)) = r_(col); l_(r_(col)) = l_(col); for_(i, col, d) for_(j, i, r) { u_(d_(j)) = u_(j); d_(u_(j)) = d_(j); --cnt_col[col_(j)]; } } void resume_(size_t col) { r_(l_(col)) = l_(r_(col)) = col; for_(i, col, u) for_(j, i, r) { u_(d_(j)) = d_(u_(j)) = j; ++cnt_col[col_(j)]; } } bool dance_(std::vector &ans_, std::function const &)> const &func_) { size_t now = r_(0); if (now == 0) return func_(ans_), true; for_(i, 0, r) if (cnt_col[i] < cnt_col[now]) now = i; remove_(now); bool ret = false; for_(i, now, d) { ans_.push_back(row_(i)); for_(j, i, r) remove_(col_(j)); ret |= dance_(ans_, func_); for_(j, i, l) resume_(col_(j)); if (!multians && ret) return true; ans_.pop_back(); } resume_(now); return ret; } void ins_row_(size_t row, const std::vector &cols) { assert(row > 0); size_t sz = data.size(); for (size_t i = 0; i < cols.size(); ++i) { data.emplace_back( sz + i - 1, sz + i + 1, u_(cols[i]), cols[i], row, cols[i]); u_(cols[i]) = d_(u_(cols[i])) = sz + i; ++cnt_col[cols[i]]; if (d_(cols[i]) == cols[i]) d_(cols[i]) = sz + i; } r_(l_(sz) = data.size() - 1) = sz; } public: explicit DLX(size_t width, bool multi_ans = false) : data(), cnt_col(), multians(multi_ans) { reset(width); } explicit DLX(std::vector> const &grid, bool multi_ans = false) : data(), cnt_col(), multians(multi_ans) { reset_grid(grid); } friend std::ostream &operator<<(std::ostream &os, DLX const &dlx) { os << dlx.data[0].l << ' ' << dlx.cnt_col.size() << ' ' << dlx.data.size() << '\n'; for (size_t i = 1; i < dlx.cnt_col.size(); ++i) os << dlx.cnt_col[i] << " \n"[i == dlx.cnt_col.size() - 1]; for (size_t i = 0; i < dlx.data.size(); ++i) os << i << ": " << dlx.data[i] << '\n'; return os; } void reset(size_t width) { assert(width > 0); data.clear(); cnt_col.resize(width + 1, 0); for (size_t i = 0; i <= width; ++i) data.emplace_back(i - 1, i + 1, i, i, 0, i); r_(l_(0) = width) = 0; } void reset_grid(std::vector> const &grid) { size_t col = grid[0].size(); for (size_t i = 1; i < grid.size(); ++i) col = std::max(col, grid[i].size()); reset(col); std::vector _; for (size_t i = 0; i < grid.size(); ++i) { _.clear(); for (size_t j = 0; j < grid[i].size(); ++j) if (grid[i][j]) _.push_back(j + 1); if (!_.empty()) ins_row_(i + 1, _); } } std::pair> dance(std::function const &)> func = [](auto const &) {}) { std::vector ans; return {dance_(ans, func), ans}; } #undef l_ #undef r_ #undef u_ #undef d_ #undef row_ #undef col_ #undef for_ }; int sdk[9][9]; template ().begin()), typename Ct::iterator> && std::is_same_v().end()), typename Ct::iterator>> * = nullptr> std::basic_ostream &operator<<(std::basic_ostream &os, const Ct &x) { if (x.begin() == x.end()) return os; for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' '; os << x.back(); return os; } const int score[9][9] = {{6, 6, 6, 6, 6, 6, 6, 6, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 9, 10, 9, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 6, 6, 6, 6, 6, 6, 6, 6}}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) cin >> sdk[i][j]; vector> maps(729, vector(324)); for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) { for (int k = 1; k <= 9; ++k) { if (sdk[i][j] && sdk[i][j] != k) continue; auto _ = (k - 1) * 81 + i * 9 + j; maps[_][i * 9 + j] = maps[_][i * 9 + k + 80] = maps[_][j * 9 + k + 161] = maps[_][(i / 3 * 3 + j / 3) * 9 + k + 242] = true; } } int max_score = -1; auto func = [&](const vector &res) { for (auto &&_ : res) { auto k = (_ - 1) / 81 + 1, i = (_ - 1) % 81 / 9, j = (_ - 1) % 9; sdk[i][j] = k; } int now_score = 0; for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) now_score += score[i][j] * sdk[i][j]; max_score = max(max_score, now_score); }; auto &&[flag, res] = DLX(maps, true).dance(func); cout << max_score; return 0; }