POJ - 1084___Square Destroyer —— IDA* | DLX重复覆盖

本文主要是介绍POJ - 1084___Square Destroyer —— IDA* | DLX重复覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

     给你$n\ast n$的由火柴组成的正方形图案$（n\le 5）$， 并对每个火柴进行编号，已经帮你删除了 $k$ 个火柴棒，请问最少还要删除几根火柴棒，使得由火柴组成的图形没有一个完整的正方形，正方形的边长可以为$1、2......$

解题思路：

    首先我们先算出，一共有$2\ast n\ast (n+1)$根火柴，$1^2+2^2+\dots +n^2=n(n+1)(2n+1)/6$个正方形，那么每个正方形只要有一个火柴缺失，这个正方形就不完整，继而转化为了DLX重复覆盖模型
    每个火柴为每一行，每个正方形为每列，要求使用最少的火柴重复覆盖每个正方形，明显套个模板就行
    只看上面的思路的话你可能会认为这道题是道水题，但发现一实现起来并不是那么简单$......$，因为本题最难的地方并不是让你想到DLX，而是怎么去建图（个人感觉）
    要注意的是他已经帮你除掉一些火柴了，那么这些火柴所涉及到的正方形永远都不完整，所以我们一开始并不着急去建图，先将需要连的点用$mark$记录下来，然后去看他已经删除了哪些火柴，然后对这些火柴涉及到的列 $j$ 进行以下操作：

dlx.L[dlx.R[j]] = dlx.L[j];
dlx.R[dlx.L[j]] = dlx.R[j];
dlx.R[j] = dlx.L[j] = 0;

    这样这列就永远删除了，最后就将$mark$记录的需要连的边连上就好，然而这并没有我我想像的那么简单，具体看下

代码思路：

    怎么处理$2\ast n\ast (n+1)$根火柴与$n(n+1)(2n+1)/6$个正方形之间的边呢？？？
    这里我是依次处理边长为$1、2......n$的正方形，设正方形的边长为 $si$，其每行就有$n-si+1$根火柴，每列也有$n-si+1$根火柴，同时每条边也会有 $si$ 根火柴
    观察每个正方形的每条边的火柴数量规律（先算边长为 $1$ 的），发现每个正方形的上边和下边满足同一个规律，左边和右边满足一个规律，用这两个规律即可建图，具体代码如下：

	int c=1;for(int si=1; si<=n; si++) {for(int i=1; i<=n-si+1; i++) {for(int j=1; j<=n-si+1; j++) {for(int k=0; k<si; k++) {mark[(i-1)*(2*n+1)+j+k][c]=true;	// 上 mark[(i-1+si)*(2*n+1)+j+k][c]=true;	// 下 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)][c]=true;	// 左 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si][c]=true;	// 右 }c++;}}}

    最后一个点！！！
    在前面我们对已经删除火柴的边所涉及到的正方形（即DLX中的列）进行删除时，记录下来这些列，在后来的加边过程中不要加这些边（这很重要，不然你会错）

核心：熟悉的使用覆盖这一技巧，同时对建图有熟练地操作

本题在没注意数据范围而调了很长时间，我真是个傻B。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define N 50010
#define M 1010
struct DancingLink {int n,s,ansd;//列数 节点总数int S[M],A[M],H[M];//S[]该列节点总数  A[]答案  H[]行首指针int L[N],R[N],U[N],D[N]; //L[],R[],U[],D[] 上下左右int X[M],C[M],vis[M];//X[] C[] 行列编号void init(int n) { //初始化this->n=n;for(int i=0; i<=n; i++)U[i]=i,D[i]=i,L[i]=i-1,R[i]=i+1;R[n]=0,L[0]=n;s=n+1;memset(S,0,sizeof(S));memset(H,-1,sizeof(H));}void DelCol(int c) { //删除列for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];}void ResCol(int c) { //恢复列for(int i=U[c]; i!=c; i=U[i])L[R[i]]=R[L[i]]=i;}void AddNode(int r,int c) { //添加节点++S[c],C[++s]=c,X[s]=r;D[s]=D[c],U[D[c]]=s,U[s]=c,D[c]=s;if(H[r]<0) H[r]=L[s]=R[s]=s;//行首节点else  R[s]=R[H[r]],L[R[H[r]]]=s,L[s]=H[r],R[H[r]]=s;}int f() {int ret=0;memset(vis,0,sizeof(vis));for(int i=R[0]; i; i=R[i])if(!vis[i]) {ret++;vis[i]=1;for(int j=D[i]; j!=i; j=D[j])for(int k=R[j]; k!=j; k=R[k])vis[C[k]]=1;}return ret;}void dfs(int d) { //深度，深搜遍历if(!R[0]) {ansd=min(d,ansd);return;}if(d+f()>=ansd) return;int c=R[0];for(int i=R[0]; i; i=R[i]) if(S[i]<S[c]) c=i;for(int i=D[c]; i!=c; i=D[i]) {DelCol(i);for(int j=R[i]; j!=i; j=R[j]) DelCol(j);dfs(d+1);for(int j=L[i]; j!=i; j=L[j]) ResCol(j);ResCol(i);}}} dlx;int main() {bool visx[80];bool mark[80][80];int n,m,cas,q;scanf("%d", &cas);while(cas--) {scanf("%d%d",&n,&q);int row=2*n*(n+1), col=0;for(int i=1; i<=n; i++) col += i*i;dlx.init(col);memset(mark,0,sizeof(mark));memset(visx,0,sizeof(visx));int c=1,tmp;for(int si=1; si<=n; si++) {for(int i=1; i<=n-si+1; i++) {for(int j=1; j<=n-si+1; j++) {for(int k=0; k<si; k++) {mark[(i-1)*(2*n+1)+j+k][c]=true;	// 上 mark[(i-1+si)*(2*n+1)+j+k][c]=true;	// 下 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)][c]=true;	// 左 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si][c]=true;	// 右 }c++;}}}for(int i=0; i<q; i++){scanf("%d", &tmp);for(int j=1; j<=col; j++){if(mark[tmp][j] && !visx[j]){visx[j] = 1;dlx.L[dlx.R[j]] = dlx.L[j];dlx.R[dlx.L[j]] = dlx.R[j];dlx.R[j] = dlx.L[j] = 0;}}}for(int i=1; i<=row; i++)for(int j=1; j<=col; j++)if(mark[i][j] && !visx[j])dlx.AddNode(i,j);dlx.ansd = 100000;dlx.dfs(0);printf("%d\n", dlx.ansd);}
}

这篇关于POJ - 1084___Square Destroyer —— IDA* | DLX重复覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---