E. Garden of the Sun 构造

E. Garden of the Sun 构造

题目大意：

给你一个 \(n*m\) 的矩阵，由 \(X\) 或者 \(.\) 构成，题目保证所有的 \(X\) 之间不共享边和点，意思是每一个 \(X\) 的附近八个方向这八个位置都没有 \(X\) ，问你是否可以将一部分的 \(.\) 换成 \(X\) 满足任意两个 \(X\) 都是连通的，并且只有一条路径（没有环）

题解：

• 考虑一些行全部变成 \(X\)
• 因为是八个方向，所以涉及三行，如果每隔两行就把一行全部变成 \(X\) ，那么只要考虑全部变成 \(X\) 的这种特殊行之间的关系就可以了
• 很容易发现处理好这些特殊行之后，我只要存在一条路径将特殊行连接就可以了
• 最后还要考虑如果最后两行都不是特殊行，就把最后一行有的在倒数第二行也放上就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 550;
char s[maxn][maxn];
int ans[maxn][maxn],n,m;
void Print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%c",ans[i][j]?‘X‘:‘.‘);
        }
        printf("\n");
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        int now = -1;
        for(int i=1;i<=n;i++){
            if(i%3==1){
                for(int j=1;j<=m;j++) ans[i][j] = 1;
                if(now==-1) now = 1;
                if(i>1) ans[i-1][now] = ans[i-2][now] = 1;
                now = -1;
            }
            else{
                for(int j=1;j<=m;j++) {
                    ans[i][j] = s[i][j] == ‘X‘;
                    if(ans[i][j]) now = j;
                }
            }
        }
        if(n%3==0){
            for(int i=1;i<=m;i++){
                if(ans[n][i]) ans[n-1][i] = 1;
            }
        }
        Print();
    }
}

E. Garden of the Sun 构造

原文：https://www.cnblogs.com/EchoZQN/p/14520304.html