离大谱!!
查看原帖
离大谱!!
581928
jasonliujiahua楼主2023/3/9 21:15

为啥bitset改成bool数组就AC了?

#include<bits/stdc++.h>
using namespace std;
const int maxn=12;
int a[maxn][maxn];
bool b[maxn][3][maxn];
inline int getnum(int i,int j)
{
    return (i-1)/3*3+(j-1)/3+1;
}
void init()
{
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            cin>>a[i][j];
            int x=getnum(i,j);
            // cout<<i<<" "<<j<<" "<<x<<endl;
            if(a[i][j]) 
                b[i][0][a[i][j]]=b[j][1][a[i][j]]=b[x][2][a[i][j]]=1;
        }
    }
}
void test1()
{
    for(int i=1;i<=9;i++)
    {
        printf("b[%d][0]=",i);
        cout<<b[i][0]<<endl;
    }
    for(int i=1;i<=9;i++)
    {
        printf("b[%d][1]=",i);
        cout<<b[i][1]<<endl;
    }
    for(int i=1;i<=9;i++)
    {
        printf("b[%d][2]=",i);
        cout<<b[i][2]<<endl;
    }
}
void output()
{
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    exit(0);
}
void dfs(int x,int y)
{
    if(a[x][y])
    {
        if(x==9 && y==9) output();
        else if(y==9) dfs(x+1,1);
        else dfs(x,y+1);
    }
    else
    {
        int z=getnum(x,y);
        for(int i=1;i<=9;i++)
        {
            if(b[x][0][i] || b[y][1][i] || b[z][2][i]) continue;
            a[x][y]=i;
            b[x][0][i]=b[y][1][i]=b[z][2][i]=1;
            if(x==9 && y==9) output();
            else if(y==9) dfs(x+1,1);
            else dfs(x,y+1);
            a[x][y]=0;
            b[x][0][i]=b[y][1][i]=b[z][2][i]=0;
        }
    }
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    init();
    // test1();
    dfs(1,1);
    return 0;
}
2023/3/9 21:15
加载中...