90TLE求调
查看原帖
90TLE求调
1436267
I_Love_Codm楼主2025/7/28 19:49
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

vector<pair<int, int>> vec;
int ans = -1;
char c[15][15];
bool vx[15][15], vy[15][15], vs[15][15];
int w[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 get_sq(int x, int y) {
    return ((x - 1) / 3) * 3 + ((y - 1) / 3) + 1;
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return w[a.first - 1][a.second - 1] > w[b.first - 1][b.second - 1];
}

void dfs(int now, int score) {
    if (now == vec.size()) {
        ans = max(ans, score);
        return;
    }

    int x = vec[now].first, y = vec[now].second;
    int k = get_sq(x, y);
    for (int i = 1; i <= 9; i++) {
        if (!vx[x][i] && !vy[y][i] && !vs[k][i]) {
            vx[x][i] = vy[y][i] = vs[k][i] = true;
            c[x][y] = i + '0';
            dfs(now + 1, score + i * w[x - 1][y - 1]);
            vx[x][i] = vy[y][i] = vs[k][i] = false;
            c[x][y] = '0';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(vx, 0, sizeof(vx));
    memset(vy, 0, sizeof(vy));
    memset(vs, 0, sizeof(vs));

    int initial_score = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> c[i][j];
            int num = c[i][j] - '0';
            if (num != 0) {
                vx[i][num] = true;
                vy[j][num] = true;
                vs[get_sq(i, j)][num] = true;
                initial_score += num * w[i - 1][j - 1];
            } else {
                vec.emplace_back(i, j);
            }
        }
    }

    sort(vec.begin(), vec.end(), cmp);
    dfs(0, initial_score);
    cout << ans << endl;
    return 0;
}
2025/7/28 19:49
加载中...