G4011 [GESP202409 四级] 黑白方块 题解

知识点：二维数组、模式匹配、枚举。

解题思路

枚举所有4×4窗口，与0000/0110/0110/0000的固定图案逐行比较，存在完全相同窗口即成功。

为什么正确

每个可能出现图案的位置都作为窗口左上角检查，完整逐格相等是出现图案的充要条件。

易错点

图案外围的0也必须匹配；矩阵小于4×4时不应越界。

复杂度

每组时间O(nm)，空间O(nm)。

参考代码（C++17）

#include<bits/stdc++.h>

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>a(n);
        for(auto &s:a)cin>>s;
        vector<string>p= {
            "0000","0110","0110","0000"
        }
        ;
        bool ok=false;
        for(int i=0;i+3<n;i++)for(int j=0;j+3<m;j++) {
            bool yes=true;
            for(int k=0;k<4;k++)if(a[i+k].substr(j,4)!=p[k])yes=false;
            ok|=yes;
        }
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。