DLX 80pts 求调

#include<bits/stdc++.h>
#define l(i) a[i].l
#define r(i) a[i].r
#define u(i) a[i].u
#define d(i) a[i].d
#define x(i) a[i].x
#define y(i) a[i].y
using namespace std;

const int N=1e6+5,M=55;
int len[12]={3,4,4,4,5,5,5,5,5,5,5,5};//每一种放置的长度 
int b[12][8][5][2]={//每一种珠子有8种情况，至多5个点，每一个点是(x,y)
    /*
    0: 原始方向
    1: 旋转90°
    2: 旋转180°
    3: 旋转270°
    4: 原始翻转
    5: 旋转90°翻转
    6: 旋转180°翻转
    7: 旋转270°翻转
    */
    //A
    {
        {{0,0},{1,0},{0,1},{-1,-1},{-1,-1}},
        {{0,0},{0,-1},{1,0},{-1,-1},{-1,-1}},
        {{0,0},{-1,0},{0,-1},{-1,-1},{-1,-1}},
        {{0,0},{0,1},{-1,0},{-1,-1},{-1,-1}},
        {{0,0},{-1,0},{0,1},{-1,-1},{-1,-1}},
        {{0,0},{0,1},{1,0},{-1,-1},{-1,-1}},
        {{0,0},{1,0},{0,-1},{-1,-1},{-1,-1}},
        {{0,0},{0,-1},{-1,0},{-1,-1},{-1,-1}}
    },
    //B
    {
        {{0,0},{0,1},{0,2},{0,3},{-1,-1}},
        {{0,0},{1,0},{2,0},{3,0},{-1,-1}},
        {{0,0},{0,-1},{0,-2},{0,-3},{-1,-1}},
        {{0,0},{-1,0},{-2,0},{-3,0},{-1,-1}},
        {{0,0},{0,1},{0,2},{0,3},{-1,-1}},
        {{0,0},{1,0},{2,0},{3,0},{-1,-1}},
        {{0,0},{0,-1},{0,-2},{0,-3},{-1,-1}},
        {{0,0},{-1,0},{-2,0},{-3,0},{-1,-1}}
    },
    //C
    {
        {{0,0},{1,0},{0,1},{0,2},{-1,-1}},
        {{0,0},{0,-1},{1,0},{2,0},{-1,-1}},
        {{0,0},{-1,0},{0,-1},{0,-2},{-1,-1}},
        {{0,0},{0,1},{-1,0},{-2,0},{-1,-1}},
        {{0,0},{-1,0},{0,1},{0,2},{-1,-1}},
        {{0,0},{0,1},{1,0},{2,0},{-1,-1}},
        {{0,0},{1,0},{0,-1},{0,-2},{-1,-1}},
        {{0,0},{0,-1},{-1,0},{-2,0},{-1,-1}}
    },
    //D
    {
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}},
        {{0,0},{1,0},{0,1},{1,1},{-1,-1}}
    },
    //E
    {
        {{0,0},{1,0},{2,0},{2,1},{2,2}},
        {{0,0},{0,-1},{0,-2},{1,-2},{2,-2}},
        {{0,0},{-1,0},{-2,0},{-2,-1},{-2,-2}},
        {{0,0},{0,1},{0,2},{-1,2},{-2,2}},
        {{0,0},{1,0},{2,0},{2,-1},{2,-2}},
        {{0,0},{0,1},{0,2},{1,2},{2,2}},
        {{0,0},{-1,0},{-2,0},{-2,1},{-2,2}},
        {{0,0},{0,-1},{0,-2},{-1,-2},{-2,-2}}
    },
    //F
    {
        {{0,0},{0,1},{1,1},{0,2},{0,3}},
        {{0,0},{1,0},{1,1},{2,0},{3,0}},
        {{0,0},{0,-1},{-1,-1},{0,-2},{0,-3}},
        {{0,0},{-1,0},{-1,-1},{-2,0},{-3,0}},
        {{0,0},{0,1},{-1,1},{0,2},{0,3}},
        {{0,0},{1,0},{1,-1},{2,0},{3,0}},
        {{0,0},{0,-1},{1,-1},{0,-2},{0,-3}},
        {{0,0},{-1,0},{-1,1},{-2,0},{-3,0}}
    },
    //G
    {
        {{0,0},{1,0},{0,1},{0,2},{1,2}},
        {{0,0},{0,-1},{1,0},{2,0},{2,-1}},
        {{0,0},{-1,0},{0,-1},{0,-2},{-1,-2}},
        {{0,0},{0,1},{-1,0},{-2,0},{-2,1}},
        {{0,0},{-1,0},{0,1},{0,2},{-1,2}},
        {{0,0},{0,1},{1,0},{2,0},{2,1}},
        {{0,0},{1,0},{0,-1},{0,-2},{1,-2}},
        {{0,0},{0,-1},{-1,0},{-2,0},{-2,-1}}
    },
    //H
    {
        {{0,0},{1,0},{0,1},{1,1},{0,2}},
        {{0,0},{0,-1},{1,0},{1,-1},{2,0}},
        {{0,0},{-1,0},{0,-1},{-1,-1},{0,-2}},
        {{0,0},{0,1},{-1,0},{-1,1},{-2,0}},
        {{0,0},{1,0},{0,-1},{1,-1},{0,-2}},
        {{0,0},{0,1},{1,0},{1,1},{2,0}},
        {{0,0},{-1,0},{0,1},{-1,1},{0,2}},
        {{0,0},{0,-1},{-1,0},{-1,-1},{-2,0}}
    },
    //I
    {
        {{0,0},{0,1},{0,2},{1,2},{1,3}},
        {{0,0},{1,0},{2,0},{2,-1},{3,-1}},
        {{0,0},{0,-1},{0,-2},{-1,-2},{-1,-3}},
        {{0,0},{-1,0},{-2,0},{-2,1},{-3,1}},
        {{0,0},{0,1},{0,2},{-1,2},{-1,3}},
        {{0,0},{1,0},{2,0},{2,1},{3,1}},
        {{0,0},{0,-1},{0,-2},{1,-2},{1,-3}},
        {{0,0},{-1,0},{-2,0},{-2,-1},{-3,-1}}
    },
    //J
    {
        {{0,0},{-1,1},{0,1},{1,1},{0,2}},
        {{0,0},{1,-1},{1,0},{1,1},{2,0}},
        {{0,0},{1,-1},{0,-1},{-1,-1},{0,-2}},
        {{0,0},{-1,1},{-1,0},{-1,-1},{-2,0}},
        {{0,0},{1,1},{0,1},{-1,1},{0,2}},
        {{0,0},{1,1},{1,0},{1,-1},{2,0}},
        {{0,0},{-1,-1},{0,-1},{1,-1},{0,-2}},
        {{0,0},{-1,-1},{-1,0},{-1,1},{-2,0}}
    },
    //K
    {
        {{0,0},{1,0},{1,1},{2,1},{2,2}},
        {{0,0},{0,1},{-1,1},{-1,2},{-2,2}},
        {{0,0},{-1,0},{-1,-1},{-2,-1},{-2,-2}},
        {{0,0},{0,-1},{1,-1},{1,-2},{2,-2}},
        {{0,0},{1,0},{1,-1},{2,-1},{2,-2}},
        {{0,0},{0,1},{1,1},{1,2},{2,2}},
        {{0,0},{-1,0},{-1,1},{-2,1},{-2,2}},
        {{0,0},{0,-1},{-1,-1},{-1,-2},{-2,-2}}
    },
    //L
    {
        {{0,0},{1,0},{0,1},{0,2},{0,3}},
        {{0,0},{0,-1},{1,0},{2,0},{3,0}},
        {{0,0},{-1,0},{0,-1},{0,-2},{0,-3}},
        {{0,0},{0,1},{-1,0},{-2,0},{-3,0}},
        {{0,0},{-1,0},{0,1},{0,2},{0,3}},
        {{0,0},{0,1},{1,0},{2,0},{3,0}},
        {{0,0},{1,0},{0,-1},{0,-2},{0,-3}},
        {{0,0},{0,-1},{-1,0},{-2,0},{-3,0}}
    }
};
char mp[M][M];int nm[M][M];//nm 是编号，mp 是原图 
struct node{
    int l,r;//左右侧
    int u,d;//上下侧
    int x,y;//当前位置
}a[N];
int tp[N];//第i行的第一个
int sz[N];//第i列的节点数 
int cnt;//动态开点
int ans[N];//如何选择 
char res[M][M];//最终答案 
struct edge{int x,y;};unordered_map<int,edge> oup;

inline void init(int m){
    //处理列，标记的是l,r
    for(int i=0;i<=m;i++){
        l(i)=i-1,r(i)=i+1;//左右侧节点 
        u(i)=d(i)=i;//不录入选择 
    } 
    l(0)=m,r(m)=0;
    cnt=m;
    memset(sz,0,sizeof sz);
    memset(tp,-1,sizeof tp);
}    
 
inline void add(int i,int j){//在链表第i行第j列放1 
    cnt++,sz[j]++;//新开节点
    x(cnt)=i,y(cnt)=j;
    u(cnt)=j,d(cnt)=d(j);
    u(d(j))=cnt;d(j)=cnt;
    if(tp[i]==-1){//当前行是空的 
        l(cnt)=r(cnt)=cnt;
        tp[i]=cnt;
    }else{
        l(cnt)=l(tp[i]),r(cnt)=tp[i];
        r(l(tp[i]))=cnt;l(tp[i])=cnt;
    }
}

inline void remove(int j){//清理第 j 列 
    r(l(j))=r(j),l(r(j))=l(j);//删除列头信息
    for(int i=d(j);i!=j;i=d(i)){//找到当前列中所有的1 
        for(int k=r(i);k!=i;k=r(k)){//清理所有包含这个1的 
            u(d(k))=u(k),d(u(k))=d(k);
            sz[y(k)]--; 
        }
    } 
}

inline void resume(int j){//完全相反 
    for(int i=u(j);i!=j;i=u(i)){//找到当前列中所有的1 
        for(int k=l(i);k!=i;k=l(k)){//清理所有包含这个1的 
            u(d(k))=k,d(u(k))=k;
            sz[y(k)]++; 
        }
    } 
    r(l(j))=j,l(r(j))=j;//重连列头信息
}

inline bool Dance(int step){
//    cout<<step<<"\n";
    if(r(0)==0){//处理完毕 
        for(int i=1;i<step;i++){
            //int id=(nm[i][j]-1)*96+opt*8+tp;
            int num=ans[i];
            int pl=num/96+1;//哪一个点 
            int x=oup[pl].x,y=oup[pl].y;
            int opt=(num%96)/8;//哪种珠子 
            int tp=num%8;//哪种情况 
            for(int j=0;j<len[opt];j++){//第几个点 
                int xx=x+b[opt][tp][j][0],yy=y+b[opt][tp][j][1];//当前位置 
                res[xx][yy]=opt+'A'; 
            }
        }
        for(int i=1;i<=10;i++){
            for(int j=1;j<=i;j++) cout<<res[i][j];
            cout<<"\n";
        }
        return 1;
    }
    int num=r(0);//找到操作最少的一列 
    for(int i=r(0);i!=0;i=r(i)) if(sz[i]<sz[num]) num=i;
    remove(num);//删除该列 
//    cout<<num<<"\n";
    for(int i=d(num);i!=num;i=d(i)){
        ans[step]=x(i);//存储对应操作，后面再解码得到信息 
        for(int j=r(i);j!=i;j=r(j)) remove(y(j));//清理信息
        if(Dance(step+1)) return 1;
        for(int j=l(i);j!=i;j=l(j)) resume(y(j));  
    }
    resume(num);//恢复信息 
    return 0;
}

int main(){
    init(67);
    int numx=0;
    for(int i=1;i<=10;i++){
        for(int j=1;j<=i;j++){
            cin>>mp[i][j];
            nm[i][j]=++numx;
            oup[numx]={i,j};
        }
    }
    for(int i=1;i<=10;i++){
        for(int j=1;j<=i;j++){
            if(mp[i][j]=='.'){//逐个枚举，往里面放 
                for(int opt=0;opt<12;opt++){//哪种珠子 
                    for(int tp=0;tp<8;tp++){//哪种放置方式 
                        bool tag=1;
                        for(int num=0;num<len[opt];num++){//第几个点 
                            int x=i+b[opt][tp][num][0],y=j+b[opt][tp][num][1];//当前位置 
                            if(x<1 || y<1 || x>10 || x<y){tag=0;break;}
                            if(mp[x][y]!='.'){tag=0;break;}
                        }
                        if(tag==1){
                            int id=(nm[i][j]-1)*96+opt*8+tp;//对应编号
                            for(int num=0;num<len[opt];num++){//第几个点 
                                int x=i+b[opt][tp][num][0],y=j+b[opt][tp][num][1];//当前位置 
                                add(id,nm[x][y]);//放入对应节点 
                            }
                            add(id,opt+56);//可以满足哪种限制 
//                            if(opt==1) cout<<i<<" "<<j<<" "<<opt<<" "<<tp<<"\n"; 
                        }
                    }
                }
            }else{//直接按照其对应的位置放 
                int opt=mp[i][j]-'A';
                for(int tp=0;tp<8;tp++){//哪种放置方式 
                    bool tag=1;
                    for(int num=0;num<len[opt];num++){//第几个点 
                        int x=i+b[opt][tp][num][0],y=j+b[opt][tp][num][1];//当前位置 
                        if(x<1 || y<1 || x>10 || x<y){tag=0;break;}
                        if(mp[x][y]!=mp[i][j]){tag=0;break;}
                    }
                    if(tag==1){
                        int id=(nm[i][j]-1)*96+opt*8+tp;//对应编号
                        for(int num=0;num<len[opt];num++){//第几个点 
                            int x=i+b[opt][tp][num][0],y=j+b[opt][tp][num][1];//当前位置 
                            add(id,nm[x][y]);//放入对应节点 
                        }
                        add(id,opt+56);//可以满足哪种限制 
//                        cout<<i<<" "<<j<<" "<<opt<<" "<<tp<<"\n"; 
                    }
                }
            }
        }
    }
    Dance(1);
    return 0;
}