题解：P13570 [CCPC 2024 重庆站] 连方

· · 题解

都能看懂题吧。

显然若有一行是满的代表整个连方都是满的。那么如果上下两行一行满一行没满，直接不可以。如果上下两行都满了，全部涂满输出即可。

处理两行都没满的情况：首先在第 2、 6 行分别做第 1、7 行的“反串”（就是把 # 变成 .，把 . 变成 #）：

####.##
....#..
???????
???????
???????
.#.#..#
#.#.##.

这样可以确保所有的 # 八连通。 在第 2 第 6 行，我们选一个 .，在他的上/下方做一个 #（注意：这个 . 左右两边必须要有 #，不然你会和其他 # 断绝联系，具体的，下面示例“图”有个 x，那里就不能放 #）。

####.##
....#..
x..#...
???????
#......
.#.#..#
#.#.##.

现在第 3 行和第 5 行各有一个 #，如何连接？

分情况，设他们的横坐标分别为 x_1,x_2（x_1\le x_2），若 x_2-x_1<2，则在第 4 行的第 x_1 格（第 x_2 格也行）涂上 #。否则在第 4 行，把区间 (x_1,x_2) 涂满即可。

####.##
....#..
...#...
.##....
#......
.#.#..#
#.#.##.

检查一下，的确是八连通，所有四连通的 # 都组成了实心矩形。完美。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 1e5+5;
char a[7][maxn];

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        for (int i = 0; i <= 6; i++) {
            for (int j = 1; j <= n; j++)
                a[i][j] = '.';
            a[i][n+1] = '\0';
        }
        scanf("%s",a[0]+1);
        scanf("%s",a[6]+1);
        int c1 = 0,c2 = 0;
        for (int j = 1; j <= n; j++)
            if (a[0][j] == '#') c1++;
        for (int j = 1; j <= n; j++)
            if (a[6][j] == '#') c2++;
        if (c1 == n && c2 == n) {
            puts("Yes");
            for (int i = 1; i <= 7; i++) {
                for (int j = 1; j <= n; j++)
                    putchar('#');
                puts("");
            }
            continue;
        }
        if (c1 == n || c2 == n) {
            puts("No");
            continue;
        }
        puts("Yes");
        for (int j = 1; j <= n; j++)
            if (a[0][j] == '.') a[1][j] = '#';
        for (int j = 1; j <= n; j++)
            if (a[6][j] == '.') a[5][j] = '#';
//      puts(a[1]+1); puts(a[5]+1); puts("---");
        int p1,p2;
        for (int j = 1; j <= n; j++)
            if (a[1][j] == '.') {
                if (a[1][j-1] != '#' && a[1][j+1] != '#') 
                    continue;
                p1 = j; a[2][j] = '#';
                break;
            }

        for (int j = 1; j <= n; j++)
            if (a[5][j] == '.') {
                if (a[5][j-1] != '#' && a[5][j+1] != '#') 
                    continue;
                p2 = j; a[4][j] = '#';
                break;
            }

        if (abs(p1-p2) <= 1)
            a[3][p1] = '#';
        else {
            if (p1 > p2) swap(p1,p2);
            for (int j = p1+1; j <= p2-1; j++)
                a[3][j] = '#';
        }
        for (int i = 0; i <= 6; i++) puts(a[i]+1);
    }
    return 0;
}