自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:41，当前版本为作者最后更新于2024-11-12 20:33:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

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

要判断网格图中是否存在一个满足条件的子矩形，可以枚举矩形的左上角坐标 $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;
}