题解：P13570 [CCPC 2024 重庆站] 连方
woshnd
·
·
题解
题意简述
给定两个字符串 a （第 1 行）, b （第 7 行），仅含 # 和 . 。
要求构造一个 7 \times n 的字符矩阵，满足：
-
第 1 行为 a ，第 7 行为 b。
-
每个四连通的 # 必须是一个实心矩形，即 若某区域四连通，则其占据的行区间 [r_1,r_2] 与列区间 [c_1,c_2]内的格子都必须是 # 。
-
所有 # 在八方向下连通（即任意两个 # 可通过上/下/左/右/对角线移动互相到达）。
极端情况
- 若 a , b 都全为
# ，直接输出 7 行 # 即可。
- 若 a , b 其中 1 个都全为
# ，直接判无解。
简单证明： 如第 3 个样例
6
######
.####.
# 构造策略
**Step 1**：先将第 $1$ 行和第 $7$ 行内互联，可进行构造互补行。
第 $2$ 行：将 $a$ 中 `#` 变为 `.` ， `.` 变为 `#`。
第 $6$ 行：将 $b$ 中 `#` 变为 `.` ， `.` 变为 `#`。
构造过后，第 $1$ 行和第 $2$ 行八连通，第 $6$ 行和第 $7$ 行八连通。
**Step 2**：再将上下的八连通相连，可在 $3-5$ 行搭桥。
在第 $2$ 行找到一个位置 $x$ ,使得 $c[2][x]$ 为 `#` ，且 $c[2][x-1]$ 或者 $c[2][x+1]$ 为 `.`。
在第 $6$ 行找到一个位置 $y$ ,使得 $c[6][y]$ 为 `#` ，且 $c[6][y-1]$ 或者 $c[6][y+1]$ 为 `.`。
**Step 3**:通过构建对角线，使全图成为八连通。
示例：
```latex
27
.######.######.####.#.#####
........####..#.......#####
```
经过第一步变为
```latex
.######.######.####.#.#####
#......#......#....#.#.....
########....##.#######.....
........####..#.......#####
```
第二步找到 $x$ 为 $2$ ,$y$ 为 $9$。
第三步变成
```latex
.######.######.####.#.#####
#......#......#....#.#.....
.#.........................
..######...................
........#..................
########....##.#######.....
........####..#.......#####
```
构造正确
# 代码示例
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char c[10][N];
int main(){
int T,cnt1,cnt2;
int n;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=7;i++){
for(int j=0;j<=n+1;j++)c[i][j]='.';
}
cnt1=cnt2=0;
for(int i=1;i<=n;i++){
cin>>c[1][i];
if(c[1][i]=='#')cnt1++;
}
for(int i=1;i<=n;i++){
cin>>c[7][i];
if(c[7][i]=='#')cnt2++;
}
if(cnt1==n&&cnt2==n){
cout<<"Yes"<<endl;
for(int i=1;i<=7;i++){
for(int j=1;j<=n;j++){
cout<<'#';
}
cout<<endl;
}
continue;
}
if(cnt1==n||cnt2==n){
cout<<"No"<<endl;
continue;
}
for(int i=1;i<=n;i++){
if(c[1][i]=='.')c[2][i]='#';
else c[2][i]='.';
}
for(int i=1;i<=n;i++){
if(c[7][i]=='.')c[6][i]='#';
else c[6][i]='.';
}
int a,b;
for(int i=1;i<=n;i++){
if(c[2][i]=='.'&&(c[2][i-1]=='#'||c[2][i+1]=='#')){
a=i;
break;
}
}
for(int i=1;i<=n;i++){
if(c[6][i]=='.'&&(c[6][i-1]=='#'||c[6][i+1]=='#')){
b=i;
break;
}
}
int l;
if(b>a)l=b-a+1;
else l=a-b+1;
if(l==3){
c[3][a]='#';
c[4][(b+a)/2]='#';
c[5][b]='#';
}
else if(l<3){
c[3][a]='#';
c[4][b]='#';
c[5][b]='#';
}
else{
c[3][a]='#';
c[5][b]='#';
if(a>b)swap(a,b);
for(int i=a+1;i<b;i++)c[4][i]='#';
}//太菜了，只会分类讨论
cout<<"Yes"<<endl;
for(int i=1;i<=7;i++){
for(int j=1;j<=n;j++){
if(c[i][j]=='#')cout<<'#';
else cout<<'.';
}
cout<<endl;
}
}
return 0;
}
```