当前位置:网站首页>Fzu 1686 dragon mystery repeated coverage
Fzu 1686 dragon mystery repeated coverage
2022-07-06 21:20:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
exchange 0,1 Model , Such as . Be careful , The range of data
#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;
}
Copyright notice : This article is the original article of the blogger , Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117105.html Link to the original text :https://javaforall.cn
边栏推荐
- 【深度学习】PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
- 【mysql】触发器
- 968 edit distance
- Why do job hopping take more than promotion?
- Deployment of external server area and dual machine hot standby of firewall Foundation
- 监控界的最强王者,没有之一!
- Notes - detailed steps of training, testing and verification of yolo-v4-tiny source code
- @PathVariable
- JS traversal array and string
- 启动嵌入式间:资源有限的系统启动
猜你喜欢
Absolute primes (C language)
[MySQL] basic use of cursor
Summary of cross partition scheme
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
HMS Core 机器学习服务打造同传翻译新“声”态,AI让国际交流更顺畅
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,
Fastjson parses JSON strings (deserialized to list, map)
防火墙基础之外网服务器区部署和双机热备
20220211 failure - maximum amount of data supported by mongodb
Swagger UI tutorial API document artifact
随机推荐
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
Deployment of external server area and dual machine hot standby of firewall Foundation
R语言做文本挖掘 Part4文本分类
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
Summary of cross partition scheme
El table table - get the row and column you click & the sort of El table and sort change, El table column and sort method & clear sort clearsort
3D人脸重建:从基础知识到识别/重建方法!
js之遍历数组、字符串
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
Aike AI frontier promotion (7.6)
MLP (multilayer perceptron neural network) is a multilayer fully connected neural network model.
js中,字符串和数组互转(二)——数组转为字符串的方法
Huawei device command
The most comprehensive new database in the whole network, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, flying Book Multidimensional table, heipayun, Zhix
OSPF multi zone configuration
SAP UI5 框架的 manifest.json
c#使用oracle存储过程获取结果集实例
首批入选!腾讯安全天御风控获信通院业务安全能力认证
JS according to the Chinese Alphabet (province) or according to the English alphabet - Za sort &az sort
Web开发小妙招:巧用ThreadLocal规避层层传值