1 条题解

  • 0
    @ 2022-08-13 21:48:43
    #include <bits/stdc++.h>//懒人专用头文件
    #define inr int
    
    #define rpt(n) for(register int ttxyc=0;ttxyc<(n);++ttxyc)//宏定义
    using namespace std;
    struct czakioi {
        int i, cnt;
        bool operator<(const czakioi cz)const {
            return cnt < cz.cnt;
        }
    } ioioi[10];
    int hang[10][11], lie[10][11], gong[10][11], kkk[100][5], ans = -1, n, sum, u[10][10];
    int findgong(int x, int y) {
        return x / 3 * 3 + y / 3;
    }
    int findscore(int x, int y) {
        if (x == 0 || x == 8 || y == 0 || y == 8)
            return 6;
    
        if (x == 1 || x == 7 || y == 1 || y == 7)
            return 7;
    
        if (x == 2 || x == 6 || y == 2 || y == 6)
            return 8;
    
        if (x == 3 || x == 5 || y == 3 || y == 5)
            return 9;
    
        return 10;
    }
    void dfs(int i, int now) {
        if (now + (n - i) * 90 <= ans)
            return;
    
        if (n == i) {
            if (ans < now)
                ans = now;
    
            return;
        }
    
        register int a = kkk[i][0], b = kkk[i][1], c = kkk[i][2], d = kkk[i][3];
    
        for (register int num = 9; num > 0; --num) {
            if (hang[a][num] || lie[b][num] || gong[c][num])
                continue;
    
            hang[a][num] = lie[b][num] = gong[c][num] = 1;
            dfs(i + 1, now + num * d);
            hang[a][num] = lie[b][num] = gong[c][num] = 0;
        }
    }
    main() {
        for (int i = 0; i < 9; ++i) {
            ioioi[i].i = i;
    
            for (int j = 0; j < 9; ++j) {
                int k;
                scanf("%d", &k);
    
                if (k) {
                    hang[i][k] = lie[j][k] = gong[findgong(i, j)][k] = 1;
                    sum += k * findscore(i, j);
                } else {
                    ++ioioi[i].cnt;
                    u[i][j] = 1;
                }
            }
        }
    
        sort(ioioi, ioioi + 9);
    
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                if (u[ioioi[i].i][j]) {
                    kkk[n][0] = ioioi[i].i;
                    kkk[n][1] = j;
                    kkk[n][2] = findgong(kkk[n][0], j);
                    kkk[n++][3] = findscore(kkk[n][0], j);
                }
    
        dfs(0, sum);
        printf("%d", ans);
    }/**/
    
  • 1

[NOIP2009 提高组] 靶形数独

信息

ID
1505
难度
7
分类
搜索与剪枝搜索 | 其他 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者