题解 AT2043 【[AGC004C] AND Grid】

原题传送门

不知道为什么翻译要把关于颜色的描述去掉，我认为这样并没有使题意得到简化。

这里再翻译一遍。

题面简述

给你一个H×W的网格图，有一些格子涂了紫色。

请你构造出两个大小相等的网格图，其中一个部分格子涂了红色，且四联通，另一个部分格子涂了蓝色，且四联通。

要求原网格紫色的位置必须对应于两个网格中的红和蓝，其余都不能同时涂红和蓝。保证边界没有紫色。

输出样例就是在放屁，如果这题谁能写出一种正解输出是样例的话这题就应该名垂青史了。

题目保证有解的话，我们留意到一个细节，边界没有紫色。

要保证四联通，最简单的当然是整个图都是一种颜色。但是这题有两种，所以考虑五五开。

但是直接从中间把这个图剪开一半一半的话，很难保证四联通。

那么想到可以两种颜色一行一行穿插，然后在绝对不会有紫色的边界各弄一列。最后的成品就像两个梳子卡在一起。

具体理解请看代码。

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
char a[510][510],red[510][510],blue[510][510];

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&a[i][j]);//目标矩阵
    for(int i=1;i<=n;i++) {red[i][m]=blue[i][1]='.'; red[i][1]=blue[i][m]='#';}//染一列
    for(int i=1;i<=n;i++)
        for(int j=2;j<m;j++)
        {
            if(i&1) {red[i][j]='#'; blue[i][j]='.';}
            else {red[i][j]='.'; blue[i][j]='#';}
            if(a[i][j] == '#') red[i][j]=blue[i][j]='#';
        }//按照奇偶和数据给定紫色涂剩下的
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) printf("%c",red[i][j]);
        puts("");
    }
    puts("");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) printf("%c",blue[i][j]);
        puts("");
    }   //直接输出
//  fclose(stdin); fclose(stdout);
    return 0;
}

时间复杂度\text{O}(n^2)，可以通过本题。

\text{Thank you for your reading!}

您的点赞和评论是对作者最大的支持！