当前位置: 代码迷 >> 综合 >> DLX精确覆盖 zoj3209 Treasure Map
  详细解决方案

DLX精确覆盖 zoj3209 Treasure Map

热度:77   发布时间:2023-12-14 03:46:12.0

传送门:点击打开链接

题意:先告诉一个一个矩阵大小n*m和有多少个矩形p,然后告诉每个矩形所在的左下角和右上角的坐标,要求矩形不能有重叠部分,求覆盖矩阵至少需要多少个矩形。

思路:DLX精确覆盖,列表示每个点,行表示矩形,那么每次将矩形和矩形中的点对应起来,需要选出一些行使得所有的列都被覆盖,这样题目就转换完成了

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1000 + 5;
const int MN = 1000000 + 5;
const