蒟蒻dancing links 0pts求调（悬1关）

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,u,d,l,r;
}a[114514*3];
int n,m,cnt,vis[114][514],n1,s[114514];
int ans[114514],cnt1,sum,ans1;
void bld()
{
    for(int i=0;i<=m;i++)
        a[i].l=i-1,a[i].r=i+1,a[i].d=a[i].u=i;
    a[0].l=m,a[m].r=0;
    for(int i=1;i<=n;i++)
    {
        int begin=cnt,end=cnt;
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j])
                continue;
            a[cnt].x=i,a[cnt].y=j;
            s[j]++;

            a[a[j].u].d=cnt;
            a[cnt].u=a[j].u;
            a[cnt].d=j;
            a[j].u=cnt;

            a[cnt].l=end;
            a[cnt].r=begin;
            a[end].r=cnt;
            a[begin].l=cnt;
            end=cnt;

            cnt++;
        }
    }
}
void del(int x)
{
    a[a[x].l].r=a[x].r;
    a[a[x].r].l=a[x].l;
    for(int i=a[x].d;i!=x;i=a[i].d)
        for(int j=a[i].r;j!=i;j=a[j].r)
        {
            a[a[j].u].d=a[j].d;
            a[a[j].d].u=a[j].u;
            s[a[i].y]--;
        }
}
void remove(int x)
{
    a[a[x].l].r=a[a[x].r].l=x;
    for(int i=a[x].d;i!=x;i=a[i].d)
        for(int j=a[i].r;j!=i;j=a[j].r)
        {
            a[a[j].u].d=a[a[j].d].u=j;
            s[a[i].y]++;
        }
}
void print()
{
    if(sum>3)
        return;
    sum++;
    for(int i=1;i<=n1;i++)
        cout<<(ans[i]-1)%n1+1<<" ";
    cout<<endl;
    return;
}
void dfs()
{
    if(a[0].r==0)
    {
        print();
        ans1++;
        return;
    }
    int minn=1e9,p=-1;
    for(int i=a[0].r;i;i=a[i].r)
        if(s[i]<minn)
        {
            minn=s[i];
            p=i;
        }
    del(p);
    for(int i=a[p].d;i!=p;i=a[i].d)
    {
        ans[++cnt1]=a[i].x;
        for(int j=a[i].r;i!=j;j=a[j].r)
            del(a[j].y);
        dfs();
        --cnt1;
        for(int j=a[i].r;i!=j;j=a[j].r)
            remove(a[j].y);
    }
    remove(p);
}

int main()
{
    cin>>n;
    n1=n;
    n*=n;
    m=n1*2+2*(2*n1-1);
    int cntt=0,cntt1=1;
    for(int i=1;i<=n;i++)
    {
        if(++cntt>n1)
            cntt1++,cntt=1;
        vis[i][cntt1]=vis[i][cntt1+n1]=1;
    }
    for(int i=1;i<=n1;i++)//N-J+I
        for(int j=1;j<=n1;j++)
            vis[(i-1)*n1+j][6*n1-(n1*2+n1-j+1)-i+1]=1;
    for(int i=1;i<=n1;i++)//i+j-1
        for(int j=1;j<=n1;j++)
            vis[(i-1)*n1+j][4*n1-2+i+j]=1;
//  for(int i=1;i<=n;i++)
//  {
//      for(int j=1;j<=m;j++)
//          cout<<vis[i][j]<<" ";
//      cout<<endl;
//  }
    bld();
    dfs();
    cout<<ans1;
}