1966B - 矩形填充 详细题解

一、题目核心操作回顾

你可以执行任意次操作： 选择两个同色格子，把它们围成的矩形内所有格子染成该颜色。 目标：判断能否把整个 $n \times m$ 网格染成同一种颜色。

二、标程核心结论

最终判断规则

输出 NO，当且仅当 满足以下任意一条： 1. 第一行全为同色 + 最后一行全为同色 + 这两行颜色不同 2. 第一列全为同色 + 最后一列全为同色 + 这两列颜色不同

其余所有情况，都输出 YES。

三、完整推导

情况1：两个对角格子颜色相同

比如左上角 $\&$ 右下角 同色 → 直接一步操作 把整个网格染成该颜色 → 答案一定是 YES

情况2：四个对角颜色交替（W B / B W）

这是唯一可能答案为 NO 的情况： 此时必须进一步检查：

1. 如果第一行不是完全相同，或者最后一行不是完全相同 → 一定可以通过两步操作铺满全场 → 答案 YES

2. 如果第一列不是完全相同，或者最后一列不是完全相同 → 一定可以通过两步操作铺满全场 → 答案 YES

3. 只有当：

• 第一行全部一色
• 最后一行全部一色
• 两行颜色不一样 或者
• 第一列全部一色
• 最后一列全部一色
• 两列颜色不一样 → 永远无法统一颜色 → 答案 NO

四、算法步骤

对每组测试用例： 1. 检查第一行是否所有字符相同 2. 检查最后一行是否所有字符相同 3. 如果两行都单色 且颜色不同 → 输出 NO 4. 检查第一列是否所有字符相同 5. 检查最后一列是否所有字符相同 6. 如果两列都单色 且颜色不同 → 输出 NO 7. 其余所有情况 → 输出 YES

五、复杂度

• 时间复杂度：$O(nm)$
• 空间复杂度：$O(nm)$ 完全符合题目数据范围。

六、代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<string> g(n);
        for (int i = 0; i < n; ++i) {
            cin >> g[i];
        }
        
        bool ok = true;
        
        // 检查：第一行全相同 && 最后一行全相同 && 颜色不同
        bool top_same = true;
        for (int j = 1; j < m; ++j) {
            if (g[0][j] != g[0][0]) top_same = false;
        }
        bool bot_same = true;
        for (int j = 1; j < m; ++j) {
            if (g[n-1][j] != g[n-1][0]) bot_same = false;
        }
        if (top_same && bot_same && g[0][0] != g[n-1][0]) {
            ok = false;
        }
        
        // 检查：第一列全相同 && 最后一列全相同 && 颜色不同
        bool left_same = true;
        for (int i = 1; i < n; ++i) {
            if (g[i][0] != g[0][0]) left_same = false;
        }
        bool right_same = true;
        for (int i = 1; i < n; ++i) {
            if (g[i][m-1] != g[0][m-1]) right_same = false;
        }
        if (left_same && right_same && g[0][0] != g[0][m-1]) {
            ok = false;
        }
        
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}