【agc004C】AND Grid

Portal --> agc004C

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");

	}

}