$$\color{Purple}{kuangbin题解目录}$$
描述
下图左侧显示了一个用 $24$ 根火柴棍构成的完整 $3×3$ 网格。
所有火柴的长度都是 $1$。
您可以在网格中找到许多不同大小的正方形。
在左图所示的网格中,有 $9$ 个边长为 $1$ 的正方形,$4$ 个边长为 $2$ 的正方形和 $1$ 个边长为 $3$ 的正方形。
组成完整网格的每一根火柴都有唯一编号,该编号从上到下,从左到右,从 $1$ 开始按顺序分配。
如果你将一些火柴棍从完整网格中取出,形成一个不完整的网格,则一部分正方形将被破坏。
右图为移除编号 $12,17$ 和 $23$ 的三个火柴棍后的不完整的 $3×3$ 网格。
这次移除破坏了 $5$ 个边长为 $1$ 的正方形,$3$ 个边长为 $2$ 的正方形和 $1$ 个边长为 $3$ 的正方形。
此时,网格不具有边长为 $3$ 的正方形,但仍然具有 $4$ 个边长为 $1$ 的正方形和 $1$ 个边长为 $2$ 的正方形。
现在给定一个(完整或不完整)的 $n \\times n$($n$ 不大于 $5$)网格,求至少再去掉多少根火柴棒,可以使得网格内不再含有任何尺寸的正方形。
输入格式
输入包含 $T$ 组测试用例。
测试用例的数量 $T$ 在输入文件的第一行中给出。
每个测试用例由两行组成:
第一行包含一个整数 $n$,表示网格的规模大小。
第二行以非负整数 $k$ 开头,表示所给网格相较完整的 $n \\times n$ 网格所缺少的火柴杆数量,后跟 $k$ 个整数表示所有缺少的火柴杆的具体编号。
注意,如果 $k$ 等于零,则表示输入网格是完整的 $n \\times n$ 网格。
输出格式
每个测试用例输出一个结果,表示破坏所有正方形,所需的去掉火柴棒的最小数量。
每个结果占一行。
输入样例:
2
2
0
3
3 12 17 23
输出样例:
3
3
思路
- 用
Dancing Links
解决,构造的01矩阵,横坐标是火柴
,纵坐标是正方形的个数
,当火柴$i$能让正方形$j$破坏掉,就0让第$i$行第$j$列为$1$,跑一遍重复覆盖问题
即可,重点难在每根火柴对其正方形的影响
判断.- 已知$n\times n$的网格需要$2\times n\times (n+1)$(每行有$n$个,共有$n+1$行,故横着的有$n\times (n+1)$根火柴,同理竖着的也有$n\times (n+1)$根火柴,共有$2\times n \times (n+1)$根火柴)根火柴,共有$\sum_{i=1}^{n}i\times i=\frac{n \times (n+1) \times (2 \times n+1)}{6} $ 个正方形(例如:$3\times 3$网格中,有$9$个边长为$1$的正方形,$4$个边长为$2$的正方形和$1$个边长为$3$的正方形).
搜索顺序
:每次选择一个还没有被覆盖的正方形(选择最小的一个
),枚举选择它的上面的哪根火柴.估价函数
: 枚举每个正方形,如果当前正方形还是完整的,那么直接删掉他的女所有边,只记删除一次.
- 正方形
横边
以它的左边
为坐标原点,竖边
以它的上边
为坐标原点,即左上角坐标为$(r,c)$,正方形长度为$len$- 例如: 在$3\times 3$的网格中,编号为$9$和编号为$12$的火柴的坐标均为$(1,1)$.
- 横着的火柴
- 在第$0$行.第$0$列横着的是编号为$1$坐标为$(0,0)$的火柴,可观察到同一行中,相邻两根横着的火柴之间的公差是$1$(在$3\times 3$的网格中,编号为$2$和编号为$3$的绝对值差为$1$);在相邻行中且在同一列中,相邻两根火柴之间的公差为$2*n+1$(例如:在$3\times 3$的网格中,编号为$2$和编号为$9$的绝对值差为$2\times 3 +1=7$);
- 故将其坐标化后,对于坐标为$(r,c)$的火柴其编号相对于坐标$(r,0)$的火柴编号
加c
,其中每一个坐标$(r,0)$的火柴编号,正好可看作是首项是1,公差为2n+1
的等差数列(已知坐标$(0,0)$的火柴编号为$1$),$n$为网格边长.- 故坐标为$(r,0)$,横着的火柴的编号为$1+(2\times n+1)\times r$;
- 故坐标为$(r,c)$,横着的火柴的编号为$\color{Red}{1+(2\times n+1)\times r+c}$(核心).
- 竖着的火柴
- 对于所有坐标$(r,c)$,竖着的火柴的编号为
当前相同坐标横着的火柴编号加n
($n$为网格边长);- 故坐标为$(r,c)$,竖着的火柴的编号为$\color{Red}{1+(2\times n+1)\times r+c +n}$(核心).
假设当前正方形的左上角坐标为$(r,c)$,边长为$len$,上下左右每条边上都有$len$根火柴(每条边上以$i$($0 \le i \le len-1$,$i$从$0$开始计数)作为偏移量,又可分为横着的火柴和竖着的火柴:
- 横着的火柴
- 对于上边从左往右的第$i$根火柴,其坐标为$(r,c+i)$,其横着的火柴的坐标为$1+(2\times n+1)\times r+(c+i)$;
- 对于下边从左往右的第$i$根火柴,其坐标为$(r+len,c+i)$,其横着的火柴的坐标为$1+(2\times n+1)\times (r+len)+(c+i)$;
- 竖着的火柴
- 对于左边从上往下的第$i$根火柴,其坐标为$(r+i,c)$,其横着的火柴的坐标为$1+(2\times n+1)\times (r+i)+c+n$;
- 对于右边从上往下的第$i$根火柴,其坐标为$(r+i,c+len)$,其横着的火柴的坐标为$1+(2\times n+1)\times (r+i)+(c+len)+n$;
代码
IDA*
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 100
using namespace std;
int t,n,m;
vector<int> square[MAXN];
int vis[MAXN];
int tempvis[MAXN];
int check(vector<int> &sq)//检查正方形是否完整
{
for(int i=0;i<sq.size();i++)
if(vis[sq[i]]==1)
return 0;
return 1;
}
int f()//估价函数
{
memcpy(tempvis,vis,sizeof(vis));//备份数组
int res=0;
for(int i=0;i<m;i++)//枚举每个正方形
{
vector<int> &sq=square[i];
if(check(sq)==1)//检查其完整性
{
res++;
for(int j=0;j<sq.size();j++)//标记其正方形所有的边
vis[sq[j]]=1;
}
}
memcpy(vis,tempvis,sizeof(vis));//还原保存的备份数据数据
return res;
}
int dfs(int root,int max_depth)
{
if(f()+root>max_depth)//剪枝
return 0;
for(int i=0;i<m;i++)//枚举所有的正方形
{
vector<int> &sq=square[i];
if(check(sq)==1)//检查其完整性
{
for(int j=0;j<sq.size();j++)//枚举该正方形的所有的边
{
int temp=sq[j];
vis[temp]=1;
if(dfs(root+1,max_depth)==1)
return 1;
vis[temp]=0;
}
//如果每条边都未成功,说明需要增加max_depth
return 0;
}
}
return 1;//所有的正方形都被破坏
}
int main()
{
cin >> t;
while(t--)
{
cin >> n;
m=0;
memset(vis,0,sizeof(vis));
for(int len=1;len<=n;len++)//枚举长度
{
//(r,c) len
//注意:默认左上角坐标为(0,0)
for(int r=0;r+len-1<=n-1;r++)//枚举横坐标
for(int c=0;c+len-1<=n-1;c++)//枚举纵坐标
{
vector<int> &sq=square[m];
sq.clear();
int d=2*n+1;
for(int i=0;i<len;i++)
{
sq.push_back(1+d*r+(c+i));//上,(r,c+i)
sq.push_back(1+d*(r+len)+(c+i));//下(r+len,c+i)
sq.push_back(1+d*(r+i)+c+n);//左(r+i,c)
sq.push_back(1+d*(r+i)+(c+len)+n);//右(r+i,c+len)
}
m++;
}
}
int k=0;
scanf("%d",&k);
while(k--)
{
int num;
cin >> num;
vis[num]=1;
}
int depth=0;
while(dfs(0,depth)==0)
depth++;
cout << depth << endl;
}
return 0;
}
Dancing Links
// Problem: 破坏正方形
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/184/
// Memory Limit: 10 MB
// Time Limit: 1000 ms
// Date: 2023-01-15 14:49:06
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 100
#define MAXM 10010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int t,n,m;
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXM];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int res;
int vis[MAXN];
int mark[MAXN][MAXN];
int temp_vis[MAXN];
int f()
{
int res=0;
memset(vis,0,sizeof(vis));
for(int i=node[0].Right;i!=0;i=node[i].Right)
if(vis[i]==0)
{
vis[i]=1;
res++;
for(int j=node[i].Down;j!=i;j=node[j].Down)
for(int k=node[j].Right;k!=j;k=node[k].Right)
vis[node[k].col]=1;
}
return res;
}
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
res=inf;
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(按顺序放)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
//与精准覆盖的差别在于删除、恢复和dance函数
void Remove_Link(int y)//删除该列
{
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
node[node[i].Right].Left=node[i].Left;
node[node[i].Left].Right=node[i].Right;
}
}
void Resume_Link(int y)//恢复该列
{
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
{
node[node[i].Right].Left=i;
node[node[i].Left].Right=i;
}
}
void dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(f()+depth>=res)//剪枝
return ;
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
res=depth;
return ;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
Remove_Link(i);//注不能是node[i].col
for(int j=node[i].Right;j!=i;j=node[j].Right)
Remove_Link(j);
dance(depth+1);
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)
Resume_Link(j);
Resume_Link(i);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> n;
int temp_row=2*n*(n+1);//火柴数
int temp_col=0;//正方形数
for(int i=1;i<=n;i++)
temp_col+=i*i;
Init_Node(temp_col);
memset(mark,0,sizeof(mark));
memset(temp_vis,0,sizeof(temp_vis));
int tot_cnt=1;
for(int len=1;len<=n;len++)
for(int r=0;r+len-1<=n-1;r++)
for(int c=0;c+len-1<=n-1;c++)
{
int d=2*n+1;
for(int i=0;i<len;i++)
{
mark[1+d*r+(c+i)][tot_cnt]=1;//上,(r,c+i)
mark[1+d*(r+len)+(c+i)][tot_cnt]=1;//下(r+len,c+i)
mark[1+d*(r+i)+c+n][tot_cnt]=1;//左(r+i,c)
mark[1+d*(r+i)+(c+len)+n][tot_cnt]=1;//右(r+i,c+len)
}
tot_cnt++;
}
int k;
cin >> k;
while(k--)
{
int num;
cin >> num;
for(int i=1;i<=temp_col;i++)//删除该正方形
if(mark[num][i]==1&&temp_vis[i]==0)
{
temp_vis[i]=1;
node[node[i].Right].Left=node[i].Left;
node[node[i].Left].Right=node[i].Right;
}
}
for(int i=1;i<=temp_row;i++)
for(int j=1;j<=temp_col;j++)
if(mark[i][j]==1&&temp_vis[j]==0)//同时这插入时也得处理
Insert_Node(i,j);
dance(0);
cout << res << endl;
}
return 0;
}