F. Fix Flooded Floor 完整题解（搭配给定标程）

一、题意概述

给定一个**$2$ 行 $n$ 列**的网格：

• .：破损格子，必须用 $1\times2$ 骨牌完全覆盖
• #：完好格子，禁止覆盖

骨牌摆放规则：

1. 竖放：占据同一列上下两个格子
2. 横放：占据同一行相邻两列格子 骨牌不可重叠、不可出界。

需要判定三种结果：

1. $\boldsymbol{\text{None}}$：不存在合法铺满方案
2. $\boldsymbol{\text{Unique}}$：有且仅有一种铺满方案
3. $\boldsymbol{\text{Multiple}}$：存在至少两种不同铺满方案

数据范围： $1\le T\le 10^4,\ 1\le n\le 2\times 10^5$，所有测试用例 $\sum n \le 2\times 10^5$，要求线性复杂度解法。

---

二、核心解题结论

1. 无解判定 从左向右逐列铺设时，出现单行孤立破损格，右侧无同行连续破损格可横放配对，直接判定无解。
2. 多解判定（最关键） 只要网格中存在连续两列构成 $2\times2$ 全破损区域（四格均为.），就一定存在两种铺设方式：
   • 方式1：左右各竖放两块骨牌
   • 方式2：上下各横放两块骨牌 出现该结构直接标记为多解。
3. 唯一解判定 全程无 $2\times2$ 全破损块，且能顺利完成所有格子铺设，则方案唯一。

---

三、算法整体思路

1. 初始化标记数组 $\mathit{vis}[2][j]$，记录位置是否已被骨牌覆盖；
2. 从左到右按列遍历网格；
3. 遍历中先检查是否存在 $2\times2$ 全空区域，标记多解状态；
4. 分三类情况贪心铺设：
   • 一列上下均为.：只能竖放，唯一选择
   • 仅上行是.：必须向右横放占用下一列同行位置
   • 仅下行是.：必须向右横放占用下一列同行位置
5. 铺设中途无法配对则判定无解；
6. 全部铺完后，根据是否存在 $2\times2$ 区块输出对应答案。

---

四、标程变量释义

string s[2];        // 存储两行网格字符串
bool vis[2][MAXN];  // vis[i][j] 表示第i行第j列是否已被覆盖
bool multi;         // 标记是否存在多解结构
bool ok;            // 标记是否存在合法铺设方案

---

五、代码逐段解析

1. 输入与初始化

cin >> n;
cin >> s[0] >> s[1];
for (int i = 0; i < 2; i++)
    for (int j = 0; j < n; j++)
        vis[i][j] = false;

读取两行网格，清空覆盖标记，为每组用例重置状态。

2. 核心遍历循环

for (int j = 0; j < n; )

采用自主控制下标遍历，横放时一次性跳过两列，竖放只跳一列。

跳过已覆盖/全完好列

if (vis[0][j] || vis[1][j]) {j++; continue;}
if (s[0][j] == '#' && s[1][j] == '#') {j++; continue;}

检测多解核心结构

if (j + 1 < n && s[0][j] == '.' && s[1][j] == '.'
    && s[0][j+1] == '.' && s[1][j+1] == '.')
{
    multi = true;
}

满足 $j,j+1$ 两列四格全为.，直接确定存在多种铺法。

情况1：当前列上下都可铺

if (s[0][j] == '.' && s[1][j] == '.')
{
    vis[0][j] = vis[1][j] = true;
    j++;
}

只能竖放骨牌，唯一铺设方式，下标右移一列。

情况2：仅上行可铺

else if (s[0][j] == '.')
{
    if (j + 1 >= n || s[0][j+1] != '.' || vis[0][j+1])
    {
        ok = false;
        break;
    }
    vis[0][j] = vis[0][j+1] = true;
    j += 2;
}

必须向右横放，若右侧不满足条件直接无解，铺设后直接跳过下一列。

情况3：仅下行可铺

else if (s[1][j] == '.')
{
    if (j + 1 >= n || s[1][j+1] != '.' || vis[1][j+1])
    {
        ok = false;
        break;
    }
    vis[1][j] = vis[1][j+1] = true;
    j += 2;
}

逻辑与上行完全一致。

3. 结果输出

if (!ok) cout << "None\n";
else if (multi) cout << "Multiple\n";
else cout << "Unique\n";

• 铺设失败 → $\text{None}$
• 存在 $2\times2$ 自由区域 → $\text{Multiple}$
• 顺利铺完且无自由区域 → $\text{Unique}$

---

六、样例对应解释

1. 样例 8 全是 . 存在大量 $2\times2$ 连续空白块 → 输出 $\text{Multiple}$
2. 样例 3 全是 # 无任何需要铺设的格子，铺设方式唯一 → 输出 $\text{Unique}$
3. 不规则残缺网格 出现单行破损格无法配对 → 输出 $\text{None}$

---

七、复杂度分析

• 时间复杂度：$O(\sum n)$，线性扫描每一列，无嵌套循环
• 空间复杂度：$O(n)$，仅使用固定二维标记数组，满足题目内存限制

---

八、易错点总结

1. 必须优先判断 $2\times2$ 区块，只要出现就一定是多解，无需后续枚举方案；
2. 横放铺设时下标必须 j+=2，避免重复遍历；
3. 不能遗漏边界判断 j+1 < n，防止数组下标越界；
4. 已经被覆盖的格子必须跳过，防止重复铺设冲突。