UVA - 11214 Guarding the Chessboard (可重复覆盖，DLX+IDA*)

题目链接

正解是IDA*+四个方向判重，但由于是个裸的可重复覆盖问题，可以用DLX水过~

每个格子与放上皇后能干掉的标记连边，跑可重复覆盖DLX。注意要用IDA*来优化，否则会超时。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+;

 int n,m,np,ka;

 char s[N][N];

 struct P {int x,y;} p[N*N];

 bool ok(P a,P b) {

     if(a.x==b.x)return ;

     if(a.y==b.y)return ;

     if(abs(a.x-b.x)==abs(a.y-b.y))return ;

     return ;

 }

 struct DLX {

     static const int N=;

     static const int M=;

     static const int MX=;

     int n,tot,S[M],H[N],vis[M];

     int row[MX],col[MX],L[MX],R[MX],U[MX],D[MX];

     void init(int _n) {

         n=_n;

         for(int i=; i<=n; ++i) {

             U[i]=D[i]=i;

             L[i]=i-,R[i]=i+;

         }

         L[]=n,R[n]=;

         tot=n+;

         memset(S,,sizeof S);

         memset(H,-,sizeof H);

         memset(vis,,sizeof vis);

     }

     void link(int r,int c) {

         int u=tot++;

         S[c]++;

         row[u]=r,col[u]=c;

         U[u]=U[c],D[u]=c;

         U[D[u]]=D[U[u]]=u;

         if(!~H[r])H[r]=L[u]=R[u]=u;

         else {

             R[u]=H[r],L[u]=L[H[r]];

             L[R[u]]=R[L[u]]=u;

         }

     }

     void remove(int c) {

         for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];

     }

     void restore(int c) {

         for(int i=U[c]; i!=c; i=U[i])L[R[i]]=R[L[i]]=i;

     }

     int h() {

         int ret=;

         for(int c=R[]; c!=; c=R[c])vis[c]=;

         for(int c=R[]; c!=; c=R[c])if(vis[c]) {

                 ++ret,vis[c]=;

                 for(int i=D[c]; i!=c; i=D[i])

                     for(int j=R[i]; j!=i; j=R[j])vis[col[j]]=;

             }

         return ret;

     }

     void check() {

         for(int c=; c<=n; ++c)if(!S[c]) {

                 for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];

                 L[R[c]]=L[c],R[L[c]]=R[c];

             }

     }

     bool dfs(int dep,int mxd) {

         if(R[]==)return ;

         if(dep+h()>mxd)return ;

         int c=R[];

         for(int i=R[]; i!=; i=R[i])if(S[i]<S[c])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);

             if(dfs(dep+,mxd))return ;

             for(int j=L[i]; j!=i; j=L[j])restore(j);

             restore(i);

         }

         return ;

     }

     int IDAStar() {for(int mxd=;; ++mxd) {if(dfs(,mxd))return mxd;}}

 } dlx;

 int main() {

     while(scanf("%d%d",&n,&m)&&n) {

         np=;

         for(int i=; i<n; ++i)scanf("%s",s[i]);

         for(int i=; i<n; ++i)

             for(int j=; j<m; ++j)if(s[i][j]=='X')p[np++]= {i,j};

         dlx.init(np);

         for(int i=; i<n; ++i)

             for(int j=; j<m; ++j)

                 for(int k=; k<np; ++k)

                     if(ok({i,j}, p[k]))dlx.link(i*m+j+,k+);

         printf("Case %d: %d\n",++ka,dlx.IDAStar());

     }

     return ;

 }