舞蹈链解法AWA

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=16*16*16+10;
const int M=16*16*4+100;
const int NM=N*M;
int r[NM],l[NM],u[NM],d[NM],row[NM],col[NM];
int h[NM],s[NM];
int ans,anss[NM],cnt,n,m;
string ch;
int tot=1;
struct node{
	int r,c,v;
}nds[NM];
char ps[16*16+10];
void inin(int _n,int _m){
	n=_n;m=_m;
	for(int i=0;i<=m;i++){
		r[i]=i+1;
		l[i]=i-1;
		u[i]=d[i]=i;
	}
	r[m]=0;
	l[0]=m;
	memset(h,-1,sizeof(h));
	memset(s,0,sizeof(s));
	cnt=m+1;
}
void cha(int R,int C){
	s[C]++;
	u[cnt]=C;
	d[cnt]=d[C];
	u[d[C]]=cnt;
	d[C]=cnt;
	row[cnt]=R;
	col[cnt]=C;
	if(h[R]<0){
		h[R]=l[cnt]=r[cnt]=cnt;
	}
	else{
		r[cnt]=h[R];
		l[cnt]=l[h[R]];
		r[l[h[R]]]=cnt;
		l[h[R]]=cnt;
	}
	cnt++;
}
void remove(int c){
	l[r[c]]=l[c];
	r[l[c]]=r[c];
	for(int i=d[c];i!=c;i=d[i]){
		for(int j=r[i];j!=i;j=r[j]){
			u[d[j]]=u[j];
			d[u[j]]=d[j];
			s[col[j]]--;
		}
	}
}
void resume(int c){
	for(int i=u[c];i!=c;i=u[i]){
		for(int j=l[i];j!=i;j=l[j]){
			u[d[j]]=j;
			d[u[j]]=j;
			s[col[j]]++;
		}
	}
	l[r[c]]=c;
	r[l[c]]=c;
}
bool dance(int deep){
	if(r[0]==0){
		ans=deep;
		return 1;
	}
	int c=r[0];
	for(int i=r[0];i!=0;i=r[i]){
		if(s[i]<s[c])c=i;
	}
	remove(c);
	for(int i=d[c];i!=c;i=d[i]){
		anss[deep]=row[i];
		for(int j=r[i];j!=i;j=r[j])remove(col[j]);
		if(dance(deep+1)==1)return 1;
		for(int j=l[i];j!=i;j=l[j])resume(col[j]);
	}
	
	resume(c);
	return 0;
}
void addcha(int r,int c,int v){
	cha(tot,(r-1)*16+c);
    cha(tot,16*16+(r-1)*16+v);
    cha(tot,16*16*2+(c-1)*16+v);
    cha(tot,16*16*3+(((r-1)/4)*4+(c-1)/4)*16+v);
    nds[tot].r=r,nds[tot].c=c,nds[tot].v=v;
    tot++;
}
int main(){
	
	while(cin>>ch){
		inin(16*16*16,16*16*4);
		tot=1;
		for(int j=1;j<=16;j++){
			if(ch[j-1]=='-'){
				for(int k=1;k<=16;k++){
					addcha(1,j,k);
				}
			}
			else{
				int k=ch[j-1]-'A'+1;
				addcha(1,j,k);
			}
		}
		for(int i=2;i<=16;i++){
			cin>>ch;
			for(int j=1;j<=16;j++){
				if(ch[j-1]=='-'){
					for(int k=1;k<=16;k++){
						addcha(i,j,k);
					}
				}
				else{
					int k=ch[j-1]-'A'+1;
					addcha(i,j,k);
				}
			}
		}
		dance(0);
		for(int i=0;i<ans;i++){
			int p=anss[i];
			ps[(nds[p].r-1)*16+nds[p].c-1]='A'+nds[p].v-1;
		}
		ps[ans]='\0';
		for(int i=0;i<16;i++){
			for(int j=0;j<16;j++){
				cout<<ps[i*16+j];
			}
			cout<<endl;
		}
		cout<<endl;
	}
	
	return 0;
}