洛谷 P1524 十字绣
2024-10-01 12:26:38
题目背景
考古学家发现了一块布,布上做有针线活,叫做“十字绣”,即交替地在布的两面穿线。
题目描述
布是一个n*m的网格,线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一,而在绣的过程中,一针中连续的两段线必须分处布的两面。给出布两面的图案(实线代表该处有线,虚线代表背面有线),问最少需要几针才能绣出来?一针是指针不离开布的一次绣花过程。
输入输出格式
输入格式:
第1行两个数N和M(1<=N,M<=200)。
接下来N行每行M个数描述正面。
再接下来N行每行M个数描述反面。
每个格子用.(表示空),/(表示从右上角连到左下角),\(表示从左上角连到右下角)和X(表示连两条对角线)表示
输出格式:
一个数,最少要用的针数。
输入输出样例
输入样例#1:
4 5
.....
.\...
..\..
.....
.....
....\
.\X..
.....
输出样例#1:
4
思路:然而我并不会(⊙o⊙)…可能是并查集吧!
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,num,sum,ans;
int map[][];
char s[][][];
int b[],c[];
int fa[],val[],vis[];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%s",s[][i]);
for(int i=;i<=n;i++)
scanf("%s",s[][i]);
for(int k=;k<=;k++)
for(int i=;i<=n;i++)
for(int j=;j<m;j++){
if(s[k][i][j]=='/'||s[k][i][j]=='X'){
if(map[j+][i]==){
num++;
fa[num]=num;
map[j+][i]=num;
}
if(map[j+][i+]==){
num++;
fa[num]=num;
map[j+][i+]=num;
}
val[map[j+][i]]+=*k-;
val[map[j+][i+]]+=*k-;
int dx=find(map[j+][i]);
int dy=find(map[j+][i+]);
if(dx!=dy) fa[dy]=dx;
}
if(s[k][i][j]==||s[k][i][j]=='X'){
if(map[j+][i]==){
num++;
fa[num]=num;
map[j+][i]=num;
}
if(map[j+][i+]==){
num++;
fa[num]=num;
map[j+][i+]=num;
}
val[map[j+][i]]+=*k-;
val[map[j+][i+]]+=*k-;
int dx=find(map[j+][i]);
int dy=find(map[j+][i+]);
if(dx!=dy) fa[dy]=dx;
}
}
for(int i=;i<=num;i++){
int dx=find(i);
if(vis[dx]==){
sum++;
c[sum]=dx;
vis[dx]=;
}
b[dx]=b[dx]+abs(val[i]);
}
for(int i=;i<=sum;i++){
if(b[c[i]]==) b[c[i]]=;
ans=ans+(b[c[i]]+)/;
}
cout<<ans;
}
最新文章
- .Net Mail SMTP 发送网络邮件
- Struts2 自定义拦截器
- MySQL 循环执行kill语句杀掉连接
- img标签中alt和title属性的正确使用
- 转:从三层架构到MVC-MVP
- c++、c实现推箱子小游戏
- [AHOI2006]文本编辑器 Splay tree区间操作
- 详解CSS网页布局中默认字体样式
- JSP自定义标签——简单标签(2)
- 程序ajax请求公共组件:app-jquery-http.js
- 操作系统:ucore的部分Bug&挑战练习
- Android简易实战教程--第十一话《获取手机所有应用信息Engine类详解》
- Shell命令-系统信息及显示之uname、hostname
- 【原创】关于Git暂存区的理解
- MiniDao支持ID自增主键策略,使用讲解
- 关于很怂地退回SDK,ndk,gradle版本这件事。。。(降版本fix项目异常)
- JSF标签之f:facet 的用法
- iOS-如何写好一个UITableView
- python模块--如何相互调用自己写的模块
- BZOJ 3022 [Balkan2012]The Best Teams(扫描线+线段树)
热门文章
- python基础,函数,面向对象,模块练习
- [terry笔记]对人员列表文件进行数据库操作
- UVA 1329	Corporative Network【并查集】
- Eclipse 更新Android SDK后,新建项目出现appcompat_v7project的相关问题
- ORACLE里锁的几种模式
- httputil用http获取请求的工具类
- mysql实战45讲 (三) 事务隔离:为什么你改了我还看不见 极客时间读书笔记
- JavaScript中Math常用方法
- pip更新问题
- Android View 上下左右四种间距的设置方法