代碼

struct DLX {int n,id;int L[maxn],R[maxn],U[maxn],D[maxn];int C[maxn],S[maxn],loc[maxn][2];void init(int nn=0) //傳列長(zhǎng) {n=nn;for(int i=0;i<=n;i++) U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;L[0]=n; R[n]=0;id=n;memset(S,0,sizeof(S));}void AddRow(int x,int col,int A[]) //傳入?yún)?shù)是行標(biāo)號(hào)，列長(zhǎng)，列數(shù)組 {bool has=false;int first=id+1;for(int y=1;y<=col;y++){if(A[y]==0) continue;has=true;++id;L[id]=id-1; R[id]=id+1;D[id]=y; U[id]=U[y];D[U[y]]=id; U[y]=id;loc[id][0]=x,loc[id][1]=y;C[id]=y; S[y]++;}if(!has) return;R[id]=first; L[first]=id;}void Remove(int Size){for(int j=D[Size];j!=Size;j=D[j])//將左右兩邊連接L[R[j]]=L[j],R[L[j]]=R[j];}void Resume(int Size){for(int j=U[Size];j!=Size;j=U[j])//恢復(fù)L[R[j]]=R[L[j]]=j;}bool vis[ms];//標(biāo)記行是否訪問(wèn)過(guò)int h() //啟發(fā)式函數(shù) {int ret=0;int i,j,k;memset(vis,0,sizeof(vis));for(i=R[0];i;i=R[i]){if(vis[i]) continue;ret++;for(j=D[i];j!=i;j=D[j]) //所有關(guān)聯(lián)的標(biāo)記了for(k=R[j];k!=j;k=R[k]) vis[C[k]]=1;}return ret;}void dfs(int step){if(step+h()>=ans) return;if(R[0]==0){ ans=min(ans,step); return; }int Min=INF,c=-1;for(int i=R[0];i;i=R[i]) if(Min>S[i]){ Min=S[i]; c=i; }for(int i=D[c];i!=c;i=D[i]){Remove(i);for(int j=R[i];j!=i;j=R[j]) Remove(j);dfs(step+1);for(int j=L[i];j!=i;j=L[j]) Resume(j);Resume(i);}return;} }dlx; View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wust-ouyangli/p/5747086.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的精确覆盖DLX算法模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。