统计矩阵中有多少个 2 × 2 子矩阵满足 D₁₁ × D₂₂ = D₁₂ × D₂₁。
给定 n 行 m 列的矩阵 A。
一个 2 × 2 的矩阵 D 是好的,当且仅当 D₁,₁ × D₂,₂ = D₁,₂ × D₂,₁。
求 A 中有多少个好的子矩阵。
2×2 子矩阵枚举左上角乘法比较行列式
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行每行 m 个整数 |
| 输出 | 好的 2×2 子矩阵个数 |
| 数据范围 | 1 ≤ n, m ≤ 500 |
| 数值范围 | −100 ≤ Aᵢⱼ ≤ 100 |
| 判定条件 | D₁₁ × D₂₂ == D₁₂ × D₂₁ |
int 完全够。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 4 | 1 × 4 = 4 | 2 × 2 = 4 | ✅ |
| (1,2) | 2 1 / 4 2 | 2 × 2 = 4 | 1 × 4 = 4 | ✅ |
| (1,3) | 1 0 / 2 1 | 1 × 1 = 1 | 0 × 2 = 0 | ❌ |
| (2,1) | 2 4 / 0 3 | 2 × 3 = 6 | 4 × 0 = 0 | ❌ |
| (2,2) | 4 2 / 3 3 | 4 × 3 = 12 | 2 × 3 = 6 | ❌ |
| (2,3) | 2 1 / 3 0 | 2 × 0 = 0 | 1 × 3 = 3 | ❌ |
(1,1) 的四个数是 1、2、2、4
两条对角乘积都是 4,相等 ✅
实际上第二行是第一行的 2 倍(成比例),所以行列式为 0
✅ 计数加 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。永远保持乘法形式,避免除零和浮点误差。双层循环枚举左上角,直接取四个元素比较
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 行 |
第一行输入 n 和 m,随后 n 行每行 m 个整数。程序会检查所有 2×2 子矩阵。
点按钮开始 →
#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 | 判定条件 | 保持乘法形式,避免除零 |
i < n,访问 A[i+1] 越界。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 4 | 2 | 题面样例 |
2 2 | 1 | 恰好只有一个子矩阵 |
2 2 | 0 | 1×4 = 4 ≠ 2×3 = 6 |
2 3 | 2 | 含 0 时乘积可能都是 0,需逐个验证 |
2 2 | 1 | 全 0 时两边乘积都是 0,成立 |
D11 / D12 == D21 / D22 在含 0 时会除零或出错,必须保持乘法。A[i][j+1],不要和 A[i+1][j] 混淆。需要存整个矩阵,500 × 500 = 25 万个 int。
✅ 25 万次判断,瞬间完成。
// 二阶行列式的几何意义 // 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 | 几何上表示向量共线/降维 | 线性代数、几何判定 |
| 窗口枚举 | 固定窗口的左上角双层循环 | 卷积、局部统计 |
a × d = b × c 等价于 a × d − b × c = 0,也就是行列式为 0;绝对值只是把"负数"也纳入,而 0 的绝对值还是 0。)