$$\color{Purple}{kuangbin题解目录}$$
描述
一张藏宝图可以看作一个 $n \\times m$ 的矩形。
给定若干张完全相同的藏宝图。
每张藏宝图都被分割为了若干个矩形碎片。
不同藏宝图的分割方式可能不同,即不同藏宝图分割得到的矩形碎片可能不尽相同。
也可能存在藏宝图没有被分割,即只获得一个大小等于藏宝图的超大矩形碎片。
为了更清晰的描述每个碎片的具体对应部位,我们不妨设藏宝图的左下角坐标为 $(0,0)$,右上角坐标为 $(n,m)$。
每个具体碎片用四个整数 $x_1,y_1,x_2,y_2$ 来描述,其中 $(x_1,y_1)$ 是碎片的左下角坐标,$(x_2,y_2)$ 是碎片的右上角坐标。
分割完毕后,将所有藏宝图碎片混合在一起,并随机拿出一部分碎片丢掉。
现在,请你判断,我们利用剩下的碎片能否拼出一张完整的藏宝图。
如果可以,请输出所需使用的碎片的最少数量。
注意,在拼藏宝图时,所选的碎片之间不得有任何重叠部分。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含三个整数 $n,m,p$,表示藏宝图的尺寸大小和剩余的碎片数量。
接下来 $p$ 行,每行包含四个整数 $x_1,y_1,x_2,y_2$,用来描述一个碎片。
输出格式
每组数据输出一行答案,如果可以拼出藏宝图,则输出所需碎片的最少数量,否则输出 $\-1$。
数据范围
$1 \\le T \\le 10$,
$1 \\le n,m \\le 30$,
$1 \\le p \\le 500$,
$0 \\le x_1 < x_2 \\le n$,
$0 \\le y_1 < y_2 \\le m$。
本题数据随机生成,保证答案不超过 $150$。
输入样例:
3
5 5 1
0 0 5 5
5 5 2
0 0 3 5
2 0 5 5
30 30 5
0 0 30 10
0 10 30 20
0 20 30 30
0 0 15 30
15 0 30 30
输出样例:
1
-1
2
样例解释
在第 $1$ 组数据中,所给的唯一碎片恰好就是完整藏宝图。
在第 $2$ 组数据中,两个碎片之间有重叠,所以无法同时选择。
在第 $3$ 组数据中,前三个碎片可以拼出完整藏宝图,后两个碎片也可以拼出完整藏宝图,所以最少需要碎片数量为 $2$。
思路
- 精确覆盖问题:给出一个$01$矩阵,选出最少的行,使得每一列恰好有一个$1$.
- 将$p$抽象成$01$矩阵的
行
,把$n\times m$的矩阵的每一个格子抽象成新$01$矩阵的列
,即有$n\times m$个列.- 新矩阵就是一个$p$行$n\times m$的$01$矩阵.
- 注意枚举每个矩形是要么采用
左开右闭
要么采用左闭右开
;- 已知点坐标$(x,y)$且大矩阵一个$n\times m$ 的矩形,若采用
左开右闭
的形式时,保证第一列一定从$1$开始,即可表示为$(x-1)\times m+y$;若采用左闭右开
的形式且由于下标是从$0$开始,故需要将坐标统一+1
,即可表示为$x\times m+y+1$.- 在插入结点时采用
链式前向星
的思想构建,即采用头插法
实现,若采用尾插法
可能存在超时的风险(我疯狂tle的原因就在此处)- 其次在
恢复现场
过程中,应注意与递归之前的执行顺序相反
即可,同时恢复与删除的过程也得相反,否则也有可能会超时.
//此处是采用左开又闭的形式
for(int x=x1+1;x<=x2;x++)
for(int y=y1+1;y<=y2;y++)
Insert_Node(i,(x-1)*m+y);//由于有head(0,0)的存在,故列至少从1开始
//此处是采用左闭又开的形式
for(int x=x1;x<x2;x++)
for(int y=y1;y<y2;y++)
Insert_Node(i,x*m+y+1);//由于有head(0,0)的存在,故列至少从1开始
代码
// Problem: 藏宝图
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4238/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-13 20:12:13
//
// 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 910
#define MAXM 450010
#define MAXP 510
//n*m*p
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int t,n,m,p;
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[MAXP];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int 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;//更新结点个数
}
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
}
void Remove_Link(int y)//删除列元素所在的列链 及 其中元素所对应行
{
//删除列链(仅需删除列元素即可删除整个列链)
node[node[y].Right].Left=node[y].Left;
node[node[y].Left].Right=node[y].Right;
//当前列元素的左面元素指向右边面的是当前元素的右面元素
//当前列元素的右面元素指向左边面的是当前元素的左面元素
for(int i=node[y].Down;i!=y;i=node[i].Down)//枚举列链中的元素
{
for(int j=node[i].Right;j!=i;j=node[j].Right)//枚举列链中元素所对应行链中元素并删除
{
node[node[j].Down].Up=node[j].Up;
node[node[j].Up].Down=node[j].Down;
//当前元素删除后,该元素的下面元素指向上面的是当前元素的上面元素
//当前元素删除后,该元素的上面元素指向下面的是当前元素的下面元素
c_cnt[node[j].col]--;//当前列的元素-1
}
}
}
void Resume_Link(int y)//恢复列元素所在列链 及 其中元素所对应行
{
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
{
for(int j=node[i].Left;j!=i;j=node[j].Left)//枚举列链中元素所对应行链中元素并恢复
{
node[node[j].Up].Down=j;
node[node[j].Down].Up=j;
//当前元素的上面元素指向下面的是当前元素
//当前元素的下面元素指向上面的是当前元素
c_cnt[node[j].col]++;//当前列的元素+1
}
}
//恢复列链(仅需恢复列元素即可恢复整个列链)
node[node[y].Left].Right=y;
node[node[y].Right].Left=y;
}
void dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(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;
Remove_Link(y);//删除列链
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
for(int j=node[i].Right;j!=i;j=node[j].Right)//删除选择行链元素所在列链
Remove_Link(node[j].col);
dance(depth+1);
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)//恢复选择行链元素所在列链
Resume_Link(node[j].col);
}
Resume_Link(y);//恢复列链
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&n,&m,&p);
Init_Node(n*m);
for(int i=1;i<=p;i++)
f_row[i]=-1;
res=inf;
for(int i=1;i<=p;i++)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(int x=x1;x<x2;x++)//此处是采用左闭又开的形式
for(int y=y1;y<y2;y++)
//已知点坐标(x,y)其数字哈希化为:x*m+y
Insert_Node(i,x*m+y+1);//由于有head(0,0)的存在,故列至少从1开始
}
dance(0);
if(res==inf)
printf("-1\n");
else printf("%d\n",res);
}
return 0;
}
妙啊,女少口阿