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

Xycxxx · 2026-01-26 20:07:19 · 题解

简单构造题。

考虑到给出的两行一定满足条件 1，所以剩下的想让格子八联通肯定是斜着交错最好，这样就不用考虑条件 1，我们先让在第 1 行和第 7 行的矩形在斜对角之间开始构造矩形使其联通，然后在斜着上去找到一个斜对角使上下联通即可。

特殊的，如果上下两行有一行全是井号，另外一行不是，则无解，容易证明。如果两行都是，那么整个都是井号。

以样例的最后一组为例：

初始为：

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

先让上下各自联通，如下：

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

然后让上下联通：

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

具体细节见代码。时间复杂度 \mathcal{O}(\sum n)。

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9')ch = getchar();
    while (ch >= '0' && ch <= '9')x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 1e5 + 5;
int n;
char a[8][N];
string s, t;
inline void solve() {
    n = rd; cin >> s >> t; s = ' ' + s, t = ' ' + t; 
    int ok1 = 1, ok2 = 1;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '.')ok1 = 0;
        if (t[i] == '.')ok2 = 0;
    }
    if (ok1 + ok2 == 1) return cout << "No" << '\n', void();
    cout << "Yes" << '\n';
    if (ok1 && ok2) {
        for (int i = 1; i <= 7; ++i) {
            for (int j = 1; j <= n; ++j)cout << '#';
            cout << '\n';
        }
        return ;
    }   
    for (int i = 1; i <= 7; ++i)for (int j = 1; j <= n; ++j)a[i][j] = '.';
    for (int i = 1; i <= n; ++i)a[1][i] = s[i], a[7][i] = t[i];
    for (int i = 1; i <= n; ++i) {
        if (a[1][i] == '.')a[2][i] = '#';
        if (a[7][i] == '.')a[6][i] = '#';
    }
    int p1 = 0, p2 = 0; 
    for (int i = 1; i <= n; ++i) {
        if (!p1 && (a[2][i + 1] == '#' || a[2][i - 1] == '#') && a[2][i] == '.')p1 = i;
        if (!p2 && (a[6][i + 1] == '#' || a[6][i - 1] == '#') && a[6][i] == '.')p2 = i;
    }
    a[5][p2] = '#', a[3][p1] = '#';
    if (p1 > p2) {
        if (p2 + 1 < p1)for (int i = p2 + 1; i < p1; ++i)a[4][i] = '#';
        else a[4][p1] = '#';
    } else if (p1 < p2) {
        if (p1 + 1 < p2)for (int i = p1 + 1; i < p2; ++i)a[4][i] = '#';
        else a[4][p1] = '#';
    } else a[4][p1] = '#';
    for (int i = 1; i <= 7; ++i) {
        for (int j = 1; j <= n; ++j)cout << a[i][j];
        cout << '\n'; 
    }
}
signed main() {
    int T = rd; while (T--)solve();
    return 0;
}