#include<bits/stdc++.h>
using namespace std;
bitset <10> canpush[3*9+1];
int sudoku[100][100],ans=0;
int sudokuser[100][100]=
{
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}
};
bool stooop=0,couted=0;
void nprint()
{
couted=1;
int nowans=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
nowans+=sudoku[i][j]*sudokuser[i][j];
ans=max(nowans,ans);
}
void findpush(int &x,int &y)
{
int nm=9;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
if(sudoku[i][j]==0)
{
int gong=((i-1)/3)*3+(j-1)/3+1;
bitset <10> tmp=canpush[i]&canpush[j+9]&canpush[gong+9+9];
int n=tmp.count();
if(n<nm)
{
nm=n;
x=i,y=j;
}
}
}
if(nm==0) stooop=1;
}
void dfs(int x,int y,int less)
{
if(x>9||y>9) return;
if(less==0) nprint();
int gong=((x-1)/3)*3+(y-1)/3+1;
bitset <10> tmp=canpush[x]&canpush[y+9]&canpush[gong+9+9];
for(int i=1;i<=9;i++)
if(tmp[i]==1)
{
sudoku[x][y]=i;
canpush[x].set(i,0);
canpush[y+9].set(i,0);
canpush[gong+9+9].set(i,0);
int nxtx,nxty;
findpush(nxtx,nxty);
if(!stooop) dfs(nxtx,nxty,less-1);
stooop=0;
sudoku[x][y]=0;
canpush[x].set(i,1);
canpush[y+9].set(i,1);
canpush[gong+9+9].set(i,1);
}
return;
}
string a;
int main()
{
int cnt0=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
cin>>sudoku[i][j];
for(int i=1;i<=27;i++) canpush[i].set();
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(sudoku[i][j]!=0)
{
int gong=((i-1)/3)*3+(j-1)/3+1;
int n=sudoku[i][j];
canpush[i].set(n,0);
canpush[j+9].set(n,0);
canpush[gong+9+9].set(n,0);
}
else cnt0++;
int fx=114514,fy=1919810,nm=9;
findpush(fx,fy);
dfs(fx,fy,cnt0);
if(couted) cout<<ans;
else cout<<-1;
return 0;
}
本机上下载过数据没问题,为什么在luogu就会爆掉,只会出-1( Linux和Win的差异吗