以为JC 。汗 -_-||
by 凉白开27du @ 2018-11-02 12:51:20
现在吸了氧A了，但是时间巨大，麻烦大佬帮我看一看
```cpp
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[1000];
struct point
{
int x,y,c;
inline void zh(int tt){x=(tt-1)/81+1;y=((tt-1)%81)/9+1;c=((tt-1)%9)+1;}
}ans[1000];
struct node
{
int l,r,u,d,lie,hang;
};
struct DLX
{
node p[210000];int len;
int size[1000],last[1000],map[11][11];
bool bol[1000];
inline void make(int l,int r,int u,int d,int lie,int hang){p[len].l=l;p[len].r=r;p[len].u=u;p[len].d=d;p[len].lie=lie;p[len].hang=hang;}
inline void sxdel(int x){p[p[x].u].d=p[x].d;p[p[x].d].u=p[x].u;}
inline void nsxdel(int x){p[p[x].u].d=p[p[x].d].u=x;}
inline void zydel(int x){p[p[x].l].r=p[x].r;p[p[x].r].l=p[x].l;}
inline void nzydel(int x){p[p[x].l].r=p[p[x].r].l=x;}
inline void clear(int x)
{
len=0;p[0].l=p[0].r=p[0].u=p[0].d=0;
for(int i=1;i<=x;i++)
{
len++;make(i-1,p[i-1].r,i,i,i,0);
nzydel(i);size[i]=0;last[i]=i;
}
}
inline void add(int row)
{
if(!a[0])return ;
len++;make(len,len,last[a[1]],p[last[a[1]]].d,a[1],row);
nsxdel(len);size[a[1]]++;last[a[1]]=len;
for(int i=2;i<=a[0];i++)
{
len++;make(len-1,p[len-1].r,last[a[i]],p[last[a[i]]].d,a[i],row);
nsxdel(len);nzydel(len);size[a[i]]++;last[a[i]]=len;
}
}
inline void del(int x)
{
zydel(x);
for(int i=p[x].u;i!=x;i=p[i].u)
{
for(int j=p[i].r;j!=i;j=p[j].r)
{
sxdel(j),size[p[j].lie]--;
}
}
}
inline void back(int x)
{
nzydel(x);
for(int i=p[x].u;i!=x;i=p[i].u)
{
for(int j=p[i].r;j!=i;j=p[j].r)nsxdel(j),size[p[j].lie]++;
}
}
inline bool dance(int x)
{
if(!p[0].r)
{
for(int i=1;i<=x;i++)
{
map[ans[i].x][ans[i].y]=ans[i].c;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=8;j++)printf("%d ",map[i][j]);
printf("%d\n",map[i][9]);
}
return true;
}
int first=0,mi=999999999;
for(int i=p[0].r;i;i=p[i].r)
{
if(size[p[i].lie]<mi)mi=size[p[i].lie],first=p[i].lie;
}
if(mi==0)return false;
del(first);
for(int i=p[first].u;i!=first;i=p[i].u)
{
for(int j=p[i].l;j!=i;j=p[j].l)del(p[j].lie);
ans[x+1].zh(p[i].hang);
if(dance(x+1))return true;
for(int j=p[i].l;j!=i;j=p[j].l)back(p[j].lie);
}
back(first);
return false;
}
}dlx;
int main()
{
memset(dlx.bol,false,sizeof(dlx.bol));
dlx.clear(4*9*9);
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
scanf("%d",&dlx.map[i][j]);
if(dlx.map[i][j])
{
dlx.bol[(i-1)*9+j]=true;
// dlx.del((i-1)*9+j);
dlx.bol[81+(i-1)*9+dlx.map[i][j]]=true;
// dlx.del(81+(i-1)*9+dlx.map[i][j]);
dlx.bol[162+(j-1)*9+dlx.map[i][j]]=true;
// dlx.del(162+(j-1)*9+dlx.map[i][j]);
dlx.bol[243+(((i-1)/3)*3+(j-1)/3)*9+dlx.map[i][j]]=true;
// dlx.del(243+(((i-1)/3)*3+(j-1)/3)*9+dlx.map[i][j]);
}
else
{
for(int k=1;k<=9;k++)
{
if(!dlx.bol[81+(i-1)*9+k] && !dlx.bol[162+(j-1)*9+k] && !dlx.bol[243+(((i-1)/3)*3+(j-1)/3)*9+k])
{
a[0]=0;
a[++a[0]]=(i-1)*9+j;
a[++a[0]]=81+(i-1)*9+k;
a[++a[0]]=162+(j-1)*9+k;
a[++a[0]]=243+(((i-1)/3)*3+(j-1)/3)*9+k;
dlx.add((i-1)*81+(j-1)*9+k);
}
}
}
}
}
for(int i=1;i<=324;i++)
{
if(dlx.bol[i])dlx.del(i);
}
dlx.dance(0);
return 0;
}
```
by 爱喝敌敌畏 @ 2018-11-02 14:21:26