求调(盐豆不带盐了
  • 板块P10482 Sudoku 2
  • 楼主liangcc
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/14 18:00
  • 上次更新2025/6/15 13:16:36
查看原帖
求调(盐豆不带盐了
1399537
liangcc楼主2025/6/14 18:00

在code::block上写的,如果把输出注释掉过样例就会直接因为不知名错误out

#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 9, M = 110;
string s;
int r[N], c[N], b[N];
bool st[M];
int stk[100], top = 0, mp[N][N] = {
    {0, 0, 0, 1, 1, 1, 2, 2, 2},
    {0, 0, 0, 1, 1, 1, 2, 2, 2},
    {0, 0, 0, 1, 1, 1, 2, 2, 2},
    {3, 3, 3, 4, 4, 4, 5, 5, 5},
    {3, 3, 3, 4, 4, 4, 5, 5, 5},
    {3, 3, 3, 4, 4, 4, 5, 5, 5},
    {6, 6, 6, 7, 7, 7, 8, 8, 8},
    {6, 6, 6, 7, 7, 7, 8, 8, 8},
    {6, 6, 6, 7, 7, 7, 8, 8, 8}
};
void init(){
    memset(r, 0, sizeof r);
    memset(c, 0, sizeof c);
    memset(b, 0, sizeof b);
    memset(st, false, sizeof st);
    return;
}
int get(){
    int minv = N, loc;
    for (int i = 0, k = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ , k ++ )
            if (!st[k] && s[k] == '.'){
                int state = r[i] | c[j] | b[mp[i][j]], t = 0;
                for(int i = 1; i <= N; i ++ ) t += !(state >> i & 1);
                if(t < minv) minv = t, loc = k;
            }
    st[loc] = true;
    return loc;
}
bool dfs(int u, string &res){
    if (u == -1) return true;
    int ne = get(), x = ne / 9, y = ne % 9;
    int state = r[x] | c[y] | b[mp[x][y]];
    for (int i = 1, j = 2; i <= N; i ++ , j <<= 1)
        if (!(state & j)){
            r[x] |= j, c[y] |= j, b[mp[x][y]] |= j;
            res[ne] = i + '0';
            if(dfs(u - 1, res)) return true;
            r[x] ^= j, c[y] ^= j, b[mp[x][y]] ^= j;
        }
    return false;
}
int main(){
    while (cin >> s, s != "end"){
        init();
//        for(int i = 0; i < N; i ++ ) cout << (bitset<32>)r[i] << endl;
//        puts("");
//        for(int j = 0; j < N; j ++ ) cout << (bitset<32>)c[j] << endl;
//        puts("");
//        for(int k = 0; k < N; k ++ ) cout << (bitset<32>)b[k] << endl;
//        puts("");
        int cnt = 0;
        string res(81, ' ');
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ , k ++ )
                if (s[k] != '.'){
                    int t = 1 << (s[k] - '0');
                    r[i] |= t, c[j] |= t, b[mp[i][j]] |= t;
                    res[k] = s[k];
                }
                else cnt ++ ;

        dfs(cnt, res);
        cout << res << endl;
    }
    return 0;
}

如果加上输出的话那么样例的第一条能过,第二条不能过。 重启之后发现不加输出第一次能过第一条,之后第一条还是会out。

会不会是内存分配的问题呢QωQ

有没有大佬解答一下。

2025/6/14 18:00
加载中...