【agc004C】AND Grid
Description
给你一个\(n*m\)的网格图\(A\),有一些格子是'#',现在要构造出两个新的网格图\(B\)和\(C\)满足:
1、如果\(A[i][j]=\)'#',则\(B[i][j]=C[i][j]=\)'#'
2、如果\(A[i][j]\neq\)'#',则\(B[i][j]=\)'#'或\(C[i][j]=\)'#'
3、\(B\)和\(C\)中的所有的'#'都只构成\(1\)个连通块
数据范围:保证\(A\)的边界没有'#',\(3<=n,m<=500\)
Solution
构造题什么的。。==
在钦定了必定为'#'的格子(也就是\(A[i][j]\)为'#'的那些\((i,j)\))之后,我们剩下要做的就是。。用两种没有交的方案把这些'#'连起来
注意到题目中有一个很奇怪的条件:\(A[i][j]\)的边界上面保证没有'#',所以要好好利用一下
具体的话就是。。考虑根据奇偶性分类,在\(B\)图中将第二维为奇数的位置全部钦定成'#',然后钦定最上面那行为'#';在\(C\)图中将第二维为偶数的位置全部钦定为'#',然后钦定最下面那行为'#'即可
然后这样一定是对的:首先肯定不会有交集,接着就是连通性,因为是根据第二维的奇偶性钦定的字符,所以\(B\)中的奇数位(和\(C\)中的偶数位)肯定都会变成。。若干条“柱子”,然后原来处在奇数位(偶数位)的'#'肯定是连通的,原来处在偶数位(奇数位)的'#'因为相邻位肯定是'#'所以也是连通的
mark:(严格来说也不算什么特别有建设性的mark吧==)一个。。比较模糊的方向。。?两个没有交的集合的找法其实不一定要。。找出一个之后钦定不能要再找另一个,而是可以从一开始就确定两类不会产生交集的大类,然后分别在里面找
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=510;
char A[N][N],B[N][N],C[N][N];
int n,m;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d\n",&n,&m);
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j)
scanf("%c",&A[i][j]),B[i][j]=A[i][j],C[i][j]=A[i][j];
scanf("\n");
}
for (int i=1;i<=m;++i) B[1][i]='#',C[n][i]='#';
for (int i=2;i<n;++i)
for (int j=2;j<m;++j)
if (j&1) B[i][j]='#';
else C[i][j]='#';
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j)
printf("%c",B[i][j]);
printf("\n");
}
printf("\n");
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j)
printf("%c",C[i][j]);
printf("\n");
}
}
最新文章
- ELK分析IIS日志
- HDFS的架构
- java并发编程学习:如何等待多个线程执行完成后再继续后续处理(synchronized、join、FutureTask、CyclicBarrier)
- Windows Azure Virtual Machine (29) 修改Azure VM 数据磁盘容量
- 扩展Exception,增加判断Exception是否为SQL引用约束异常方法!
- hdu - 2083 - 简易版之最短距离
- jquery的上传控件uploadly,每行都有一个这样的控件对id选择器的使用
- 做SqlDependency总结的一些经验
- 《Java并发编程实战》第十五章 原子变量与非堵塞同步机制 读书笔记
- ToDoList-学习中看到的知识盲点
- android学习9——Handler简单用法
- python学习之路基础篇(第八篇)
- 关于 i++ 与 ++i
- CentOS7.4部署Python3+Django+uWSGI+Nginx
- python写service时全局变量问题
- 继承之es5对比es6
- 【apache tika】apache tika获取文件内容(与FileUtils的对比)
- 五,mysql优化——sql语句优化小技巧
- HDU 6315 Naive Operations(线段树+区间维护)多校题解
- SqlParameter 2