Agc004_C AND Grid

题目大意

给定一个$N\times M\space(N,M\leq 500)$的网格，有一些格子是紫色，保证边界没有颜色。

构造两个$N\times M$的网格$A,B$，在$A$中染红色在$B$中染蓝色，使得$A,B$内染色的格子恰好形成一个四连通块，且同一位置$A,B$均染色当且仅当原网格图中该位置染了紫色。

题解

由于边界没有颜色，不妨尝试通过某种方式将一个紫色的格子连接到上边界在把整个上边界涂色。

直接将所有紫色的点暴力的向上染色显然是不成立的，但是有一个明显的规律，每一个紫点只要存在两侧列中有一列与上边连通即可。

那么假设我们现在要染红色，首先先把原网格中紫色的点染成红色，一种合法方案是将最上方一行染成红色，再将所有除了最下方一行的其余部分的奇数列染成红色，那么对于所有的原网格中紫色的点其位置上一定有红色的点，且它们均与最上方那一行连通。不难发现，将这个方法推广到下边界上，将染奇数列变成染偶数列，一定恰好是一组合法的方案。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 510

using namespace std;

int read(){

	int nm=0,fh=1; int cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

char ch[M][M]; int n,m;

int main(){

	n=read(),m=read();

	for(int i=1;i<=n;i++) scanf("%s",ch[i]+1);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(ch[i][j]=='#') putchar('#');

			else if(i==1||(i<n&&(j&1))) putchar('#');

			else putchar('.');

		} putchar('\n');

	} putchar('\n');

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(ch[i][j]=='#') putchar('#');

			else if(i==n||(i>1&&!(j&1))) putchar('#');

			else putchar('.');

		} putchar('\n');

	}

	return 0;

}

巴特西

Agc004_C AND Grid

最新文章

热门文章