当前位置:网站首页>FZU 1686 龙之谜 重复覆盖
FZU 1686 龙之谜 重复覆盖
2022-07-06 12:56:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
兑换0,1模型,如。注意,数据的范围
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
using namespace std;
const int MaxM = 500;
const int MaxN = 500;
const int maxnode = MaxM*MaxN;
int K,n,m;
struct DLX
{
int n,m,size;
int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
int H[MaxN],S[MaxM];
int ands,ans[MaxN];
void init(int _n,int _m)
{
ands=0x3f3f3f3f;
n = _n;
m = _m;
for(int i = 0;i <= m;i++)
{
S[i] = 0;
U[i] = D[i] = i;
L[i] = i-1;
R[i] = i+1;
}
R[m] = 0; L[0] = m;
size = m;
for(int i = 1;i <= n;i++)
H[i] = -1;
}
void Link(int r,int c)
{
++S[Col[++size]=c];
Row[size] = r;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if(H[r] < 0)H[r] = L[size] = R[size] = size;
else
{
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
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 resume(int c)
{
for(int i = U[c];i != c;i = U[i])
L[R[i]]=R[L[i]]=i;
}
bool v[maxnode];
int f()
{
int ret = 0;
for(int c = R[0];c != 0;c = R[c])v[c] = true;
for(int c = R[0];c != 0;c = R[c])
if(v[c])
{
ret++;
v[c] = false;
for(int i = D[c];i != c;i = D[i])
for(int j = R[i];j != i;j = R[j])
v[Col[j]] = false;
}
return ret;
}
void Dance(int d)
{
if(d+f()>=ands) return;
if(R[0] == 0) {ands=min(ands,d);return;}
int c = R[0];
for(int i = R[0];i != 0;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);
Dance(d+1);
for(int j = L[i];j != i;j = L[j])resume(j);
resume(i);
}
}
}g;
int mp[20][20],sa,sb,id[20][20];
int main()
{
while(~scanf("%d%d",&n,&m))
{
int tot=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]) id[i][j]=++tot;
}
}
scanf("%d%d",&sa,&sb);
g.init(n*m,tot);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
for(int ii=i,cnt=1;cnt<=sa&&ii<n;ii++,cnt++)
{
for(int jj=j,cnt2=1;cnt2<=sb&&jj<m;jj++,cnt2++)
{
if(mp[ii][jj])
{
g.Link(i*m+j+1,id[ii][jj]);
}
}
}
}
}
g.Dance(0);
printf("%d\n",g.ands);
}
return 0;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117105.html原文链接:https://javaforall.cn
边栏推荐
- Math symbols in lists
- OSPF multi zone configuration
- R language visualizes the relationship between more than two classification (category) variables, uses mosaic function in VCD package to create mosaic plots, and visualizes the relationship between tw
- 字符串的使用方法之startwith()-以XX开头、endsWith()-以XX结尾、trim()-删除两端空格
- Nodejs教程之Expressjs一篇文章快速入门
- Redis insert data garbled solution
- JS according to the Chinese Alphabet (province) or according to the English alphabet - Za sort &az sort
- 2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
- Study notes of grain Mall - phase I: Project Introduction
- ICML 2022 | Flowformer: 任务通用的线性复杂度Transformer
猜你喜欢
SAP Fiori应用索引大全工具和 SAP Fiori Tools 的使用介绍
New database, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, Feishu multidimensional table, heipayun, Zhixin information, YuQue
Why do job hopping take more than promotion?
2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
2022菲尔兹奖揭晓!首位韩裔许埈珥上榜,四位80后得奖,乌克兰女数学家成史上唯二获奖女性
Comprehensive evaluation and recommendation of the most comprehensive knowledge base management tools in the whole network: flowus, baklib, jiandaoyun, ones wiki, pingcode, seed, mebox, Yifang cloud,
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条
Data Lake (VIII): Iceberg data storage format
1500萬員工輕松管理,雲原生數據庫GaussDB讓HR辦公更高效
【深度学习】PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
随机推荐
Reflection operation exercise
Comprehensive evaluation and recommendation of the most comprehensive knowledge base management tools in the whole network: flowus, baklib, jiandaoyun, ones wiki, pingcode, seed, mebox, Yifang cloud,
防火墙基础之外网服务器区部署和双机热备
全网最全的新型数据库、多维表格平台盘点 Notion、FlowUs、Airtable、SeaTable、维格表 Vika、飞书多维表格、黑帕云、织信 Informat、语雀
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
document.write()的用法-写入文本——修改样式、位置控制
What's the best way to get TFS to output each project to its own directory?
启动嵌入式间:资源有限的系统启动
Manifest of SAP ui5 framework json
Laravel笔记-自定义登录中新增登录5次失败锁账户功能(提高系统安全性)
【mysql】触发器
ICML 2022 | flowformer: task generic linear complexity transformer
Deployment of external server area and dual machine hot standby of firewall Foundation
【滑动窗口】第九届蓝桥杯省赛B组:日志统计
Le langage r visualise les relations entre plus de deux variables de classification (catégories), crée des plots Mosaiques en utilisant la fonction Mosaic dans le paquet VCD, et visualise les relation
Laravel notes - add the function of locking accounts after 5 login failures in user-defined login (improve system security)
Variable star --- article module (1)
Hardware development notes (10): basic process of hardware development, making a USB to RS232 module (9): create ch340g/max232 package library sop-16 and associate principle primitive devices