B4040 [GESP202409 四级] 黑白方块

本题考察了二维数组以及模拟、枚举算法。

要判断网格图中是否存在一个满足条件的子矩形，可以枚举矩形的左上角坐标 x 行 y 列，可以不重不漏地提取子矩形进行判断。假设判断的过程编写函数 check，且 flag 为 true 时表示存在，那么代码如下：

for (int i = 1; i <= n - 3; i++) {
    for (int j = 1; j <= m - 3; j++) {
        if (check(i, j))
            flag = true;
    }
}

题目中要求的子矩形具有形状特征，可以使用常量数组记录这个子矩形，以便判断提取的子矩形是否与之相同。

const char g[4][4] = {
    '0', '0', '0', '0',
    '0', '1', '1', '0',
    '0', '1', '1', '0',
    '0', '0', '0', '0'
};

判断函数可以如下文编写，其中 i,j 表示常量数组的第 i 行第 j 列，将其加在 x,y 上就表示以 x 行 y 列作为左上角坐标的子矩阵的对应行或者列。

例如，当 x=3,y=3 时，提取的子矩阵是第 3\sim 6 行，第 3\sim 6 列的矩阵。此时若 i=2,j=3，则相当于拿原矩阵第 5 行第 6 列的元素与 g 数组的第 3 行第 4 列（注意 g 数组下标从 0 开始）进行比较。而原矩阵第 5 行第 6 列即为提取出的子矩阵的第 3 行第 4 列。

bool check(int x, int y) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (c[i + x][j + y] != g[i][j])
                return false;
        }
    }
    return true;
}