P1074 [NOIP2009 提高组] 靶形数独
  • Code

    #include<iostream>
    using namespace std;
    #define uint unsigned
    #define uch unsigned char
    #define poi const uch&
    const unsigned scores[10][10]{
        {},
        {0,6U,6U,6U,6U,6U,6U,6U,6U,6U},
        {0,6U,7U,7U,7U,7U,7U,7U,7U,6U},
        {0,6U,7U,8U,8U,8U,8U,8U,7U,6U},
        {0,6U,7U,8U,9U,9U,9U,8U,7U,6U},
        {0,6U,7U,8U,9U,10,9U,8U,7U,6U},
        {0,6U,7U,8U,9U,9U,9U,8U,7U,6U},
        {0,6U,7U,8U,8U,8U,8U,8U,7U,6U},
        {0,6U,7U,7U,7U,7U,7U,7U,7U,6U},
        {0,6U,6U,6U,6U,6U,6U,6U,6U,6U}
    };
    const unsigned in[10][10]{
        {},
        {0,1,1,1,2,2,2,3,3,3},
        {0,1,1,1,2,2,2,3,3,3},
        {0,1,1,1,2,2,2,3,3,3},
        {0,4,4,4,5,5,5,6,6,6},
        {0,4,4,4,5,5,5,6,6,6},
        {0,4,4,4,5,5,5,6,6,6},
        {0,7,7,7,8,8,8,9,9,9},
        {0,7,7,7,8,8,8,9,9,9},
        {0,7,7,7,8,8,8,9,9,9}
    };
    bool row[10][10], col[10][10], grp[10][10], slct[10][10];
    uint ans = 0;
    uch rowcnt[10], colcnt[10];
    uch mp[10][10];
    /*
    
    *------------> (a row)
    |        x
    |
    |
    |  y
    V
    (a col)
    */
    inline void getmincnt(uch& nx, uch& ny) {
        uch maxcnt = 0;
        for (uch i = 1; i <= 9; ++i)
            if (rowcnt[i] >= maxcnt && rowcnt[i] < 9)
                nx = i, maxcnt = rowcnt[i];
        maxcnt = 0;
        for (uch i = 1; i <= 9; ++i)
            if (colcnt[i] >= maxcnt && (!slct[nx][i]))
                ny = i, maxcnt = colcnt[i];
    }
    
    void fullof(poi x, poi y, poi cnt, const unsigned& score, const unsigned& maxsc) {
    
    
        if (cnt == 81)
            return void(ans = max(ans, score));
        if (maxsc * 9ull + score * 1ull + 9ull <= ans) return;
    
        for (uch i = 1; i <= 9; ++i) {
            if (row[x][i] || col[y][i] || grp[in[x][y]][i])
                continue;
            mp[x][y] = i;
            ++rowcnt[x], ++colcnt[y];
            row[x][i] = col[y][i] = grp[in[x][y]][i] = 1;
            slct[x][y] = 1;
    
            uch nx = 0, ny = 0;
            getmincnt(nx, ny);
            fullof(nx, ny, cnt + 1, score + i * scores[x][y], maxsc - i);
    
            slct[x][y] = 0;
            row[x][i] = col[y][i] = grp[in[x][y]][i] = 0;
            --rowcnt[x], --colcnt[y];
            mp[x][y] = 0;
        }
    
    }
    
    int tmp, cnt = 0;
    
    signed main() {
        uint ms = 0;
        for (uch i = 1; i <= 9; ++i) {
            for (uch j = 1; j <= 9; ++j) {
                cin >> tmp;
                if (mp[i][j] = tmp; tmp != 0) {
                    slct[i][j] = 1;
                    ms += tmp * scores[i][j];
                    row[i][tmp] = true;
                    col[j][tmp] = true;
                    grp[in[i][j]][tmp] = true;
                    rowcnt[i]++, colcnt[j]++;
                    cnt++;
                }
            }
        }
        uint tmpr = 0, r, tmpc = 0, c;
        for (uint i = 1; i <= 9; ++i)
            if (rowcnt[i] > tmpr && rowcnt[i] < 9)
                tmpr = rowcnt[i], r = i;
        for (uint j = 1; j <= 9; ++j)
            if (colcnt[j] > tmpc && (!slct[r][j]))
                tmpc = colcnt[j], c = j;
        fullof(r, c, cnt, ms, 405);
        if (ans)
            cout << ans;
        else
            cout << "-1";
    }
    
  • Tip

    注意下标顺序

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇