GESP 题解库 / 4 级题解 / [GESP202503 四级] 二阶矩阵 · 第 9 / 25 题
GESP202503 四级 · B4264 · 入门

二阶矩阵

统计矩阵中有多少个 2 × 2 子矩阵满足 D₁₁ × D₂₂ = D₁₂ × D₂₁。

📊
n, m ≤ 500
矩阵规模
🔢
|Aᵢⱼ| ≤ 100
数值范围
⚡
O(n × m)
时间复杂度
🎯
枚举左上角
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 行 m 列的矩阵 A。

一个 2 × 2 的矩阵 D 是好的,当且仅当 D₁,₁ × D₂,₂ = D₁,₂ × D₂,₁。

求 A 中有多少个好的子矩阵。

💡
人话翻译:把每个 2 × 2 的小方块都取出来,算两条对角线的乘积是否相等——相等就计数。这个条件其实就是"二阶行列式为 0",在数学上表示"两行(或两列)成比例"。

🔍 关键词提取

2×2 子矩阵枚举左上角乘法比较行列式

已知条件

项目说明
输入第一行 n、m;随后 n 行每行 m 个整数
输出好的 2×2 子矩阵个数
数据范围1 ≤ n, m ≤ 500
数值范围−100 ≤ Aᵢⱼ ≤ 100
判定条件D₁₁ × D₂₂ == D₁₂ × D₂₁

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 枚举左上角 + 比对角乘积
📥 读入
n、m ≤ 500
值域 −100 ~ 100
乘积最大 10⁴
int 足够
🔍 枚举
左上角 (i, j)
i 从 0 到 n−2
j 从 0 到 m−2
共 (n−1)(m−1) 个
✅ 判定
取四个元素
D₁₁=a[i][j]、D₂₂=a[i+1][j+1]
D₁₂=a[i][j+1]、D₂₁=a[i+1][j]
比乘积是否相等
⚠️ 易错点
循环上界写成 i < n
四个元素取错位置
用了除法代替乘法
负数情况
03
样例手算推导
样例 6 个候选逐个验证

🧮 样例:3 × 4 矩阵,答案 2

1 2 1 0
2 4 2 1
0 3 3 0

n = 3、m = 4,所以有 (3−1) × (4−1) = 6 个候选子矩阵。

左上角D 的四个元素(第一行 / 第二行)D₁₁×D₂₂D₁₂×D₂₁好的?
(1,1)1 2 / 2 41 × 4 = 42 × 2 = 4✅
(1,2)2 1 / 4 22 × 2 = 41 × 4 = 4✅
(1,3)1 0 / 2 11 × 1 = 10 × 2 = 0❌
(2,1)2 4 / 0 32 × 3 = 64 × 0 = 0❌
(2,2)4 2 / 3 34 × 3 = 122 × 3 = 6❌
(2,3)2 1 / 3 02 × 0 = 01 × 3 = 3❌
1
为什么前两个是"好的"?

(1,1) 的四个数是 1、2、2、4

两条对角乘积都是 4,相等 ✅

实际上第二行是第一行的 2 倍(成比例),所以行列式为 0

✅ 计数加 2

2
其余为什么不是?

如 (1,3):1 × 1 = 1,但 0 × 2 = 0,不相等

如 (2,1):2 × 3 = 6,但 4 × 0 = 0,不相等

❌ 不计数

答案 2 ✓

🔑
为什么不能把等式改写成除法?因为 D₁₁ × D₂₂ = D₁₂ × D₂₁ 两边都可能为 0,一旦写成 D₁₁ / D₁₂ = D₂₁ / D₂₂ 就会出现除以 0。永远保持乘法形式,避免除零和浮点误差。
04
解法对比
枚举左上角 vs 逐行滑窗

⚔️ 解法对比

🟢 枚举左上角(推荐) 推荐

双层循环枚举左上角,直接取四个元素比较

  • 时间 O(n × m)
  • 代码 8 行
  • 逻辑最直观
  • 不需要额外空间
💡
实现要点:for (i = 0; i + 1 < n; i++)、for (j = 0; j + 1 < m; j++),这样天然保证不会越界。

🟠 先固定两行再滑列

先枚举上下两行 i、i+1,再让列 j 滑动比较

  • 复杂度完全一样
  • 代码层次更多
  • 好处是便于复用行数据
  • 本题没必要
⚠️
等价写法:两种枚举顺序结果相同。当窗口是"两行 + 多列"时,固定行的写法有时更方便,比如可以在列方向用前缀信息做优化。

📈 性能对比

方案时间复杂度代码量
枚举左上角O(n × m)约 8 行
固定两行滑列O(n × m)约 12 行
05
算法流程图
枚举左上角并比较对角乘积
开始读入 n、m 和矩阵 A;ans = 0i 从 0 到 n − 2j 从 0 到 m − 2取四个元素:D11=A[i][j]、D12=A[i][j+1]、D21=A[i+1][j]、D22=A[i+1][j+1]D11 × D22 == D12 × D21 吗?是 ✓ans 加 1否 ✗不计数输出 ans结束还有左上角 → j 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 好的二阶矩阵查找器

第一行输入 n 和 m,随后 n 行每行 m 个整数。程序会检查所有 2×2 子矩阵。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int A[505][505];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &A[i][j]);

    int ans = 0;
    // 枚举 2×2 子矩阵的左上角
    for (int i = 0; i + 1 < n; i++) {
        for (int j = 0; j + 1 < m; j++) {
            // 四个元素
            int d11 = A[i][j],     d12 = A[i][j + 1];
            int d21 = A[i + 1][j], d22 = A[i + 1][j + 1];

            if (d11 * d22 == d12 * d21) ans++;
        }
    }

    printf("%d\n", ans);
    return 0;
}
🔑
循环条件写 i + 1 < n 而不是 i < n - 1 有什么好处?两种写法等价,但 i + 1 < n 直接表达"右下角的行 i+1 必须还在矩阵内",与访问 A[i+1][...] 的形式对应,更不容易写错边界。写二维网格的窗口题时,这是一个很好用的习惯。

📖 关键几行怎么看

代码作用为什么这样写
i + 1 < n保证右下角不越界与 A[i+1] 的访问形式对应
d11 = A[i][j]主对角左上行 i、列 j
d22 = A[i+1][j+1]主对角右下行 i+1、列 j+1
d11 * d22 == d12 * d21判定条件保持乘法形式,避免除零
⚠️
三个坑:① 四个元素的位置取错(比如把 D₁₂ 写成 A[i+1][j]);② 把等式改写成除法,遇到 0 时崩溃或结果错误;③ 循环上界写成 i < n,访问 A[i+1] 越界。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 4
1 2 1 0 / 2 4 2 1 / 0 3 3 0
2题面样例
2 2
1 2 / 2 4
1恰好只有一个子矩阵
2 2
1 2 / 3 4
01×4 = 4 ≠ 2×3 = 6
2 3
1 0 0 / 0 0 1
2含 0 时乘积可能都是 0,需逐个验证
2 2
0 0 / 0 0
1全 0 时两边乘积都是 0,成立
✅
自查清单:① 四个元素取对了吗?② 用的是乘法比较吗?③ 循环上界对吗?

🚨 易错点清单

⚠️
把等式改成除法:D11 / D12 == D21 / D22 在含 0 时会除零或出错,必须保持乘法。
⚠️
四个元素位置取错:D₁₂ 是"第 1 行第 2 列",即 A[i][j+1],不要和 A[i+1][j] 混淆。
⚠️
循环越界:左上角行下标最大是 n − 2,列下标最大是 m − 2。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × m)
空间复杂度
O(n × m)
n, m 最大
500
最坏运算
约 2.5 × 10⁵

时间怎么算的?

空间都用在哪?

需要存整个矩阵,500 × 500 = 25 万个 int。

✅ 25 万次判断,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 二阶行列式的几何意义
// det = D11*D22 - D12*D21
// det == 0  <=>  两行(或两列)线性相关(成比例)
// 例如 [1 2; 2 4] 的第二行是第一行的 2 倍 -> det = 0

// 判断是否成比例(用交叉相乘避免除法)
bool proportional(int a, int b, int c, int d) {
    return a * d == b * c;      // 不要写成 a/b == c/d
}

// 扩展到 3×3 行列式(Sarrus 法则)
// det = a11*a22*a33 + a12*a23*a31 + a13*a21*a32
//     - a13*a22*a31 - a11*a23*a32 - a12*a21*a33

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
交叉相乘用乘法代替除法比较比例所有"判断成比例"的题目
行列式为 0几何上表示向量共线/降维线性代数、几何判定
窗口枚举固定窗口的左上角双层循环卷积、局部统计
🌟
思考题:如果题目改成"有多少个 2 × 2 子矩阵的行列式绝对值等于 0",答案会变吗?(提示:完全一样——因为 a × d = b × c 等价于 a × d − b × c = 0,也就是行列式为 0;绝对值只是把"负数"也纳入,而 0 的绝对值还是 0。)