二阶矩阵 题解

题目分析

题目给定一个 (n \times m) 的矩阵 (A)，定义一个 (2 \times 2) 的子矩阵 (D) 是“好的”，当且仅当其元素满足：
[
D_{1,1} \times D_{2,2} = D_{1,2} \times D_{2,1}
]
也就是说，主对角线的乘积等于副对角线的乘积。我们的任务是统计矩阵 (A) 中所有 (2 \times 2) 的“好的”子矩阵的个数。

解题思路

子矩阵的选取方式

在 (n \times m) 的矩阵中，一个 (2 \times 2) 的子矩阵可以由它的左上角位置确定。
假设左上角元素为 (A_{i,j})，那么子矩阵的四个元素分别是：

• (A_{i,j}) （左上）
• (A_{i,j+1}) （右上）
• (A_{i+1,j}) （左下）
• (A_{i+1,j+1}) （右下）

其中 (i) 的取值范围是 (1 \le i \le n-1)，(j) 的取值范围是 (1 \le j \le m-1)。

判断条件

对于每一个左上角 ((i, j))，我们只需要检查公式是否成立：
[
A_{i,j} \times A_{i+1,j+1} = A_{i+1,j} \times A_{i,j+1}
]
如果成立，计数器加一。

边界情况

• 当 (n < 2) 或 (m < 2) 时，不存在任何 (2 \times 2) 的子矩阵，答案为 (0)。
  题目数据范围保证了矩阵至少能容纳子矩阵，但我们仍可以在代码中通过循环条件自然地跳过这些情况。

算法说明

采用暴力枚举的方法，遍历所有可能的左上角位置，逐一验证即可。

具体步骤：

1. 读入 (n, m) 和矩阵 (A)。
2. 初始化答案变量 ans = 0。
3. 用两层循环遍历所有可能的左上角：
   • 外层循环 i 从 1 到 n-1
   • 内层循环 j 从 1 到 m-1
4. 对于每个 (i, j)，判断：
   [
   A[i][j] \times A[i+1][j+1] == A[i+1][j] \times A[i][j+1]
   ]
   如果相等，ans 加 1。
5. 输出 ans。

因为每个 (2 \times 2) 子矩阵的判断只涉及常数次乘法和比较，所以算法非常高效。

时间复杂度分析

需要检查的子矩阵数量为 ((n-1) \times (m-1)) 个。
对于每个子矩阵，判断的时间是 (O(1))。
总时间复杂度为 (O(nm))。
在题目给定的数据范围下（(n, m \le 500)），运算量大约在 (2.5 \times 10^5) 级别，完全可以在时间限制内完成。

空间复杂度为 (O(nm))，用于存储矩阵。

参考代码及解释

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 505;
5int n, m;
6int a[N][N];    // 存储矩阵，下标从1开始
7int ans;        // 记录答案
8
9int main() {
10    // 读入矩阵的行数和列数
11    scanf("%d%d", &n, &m);
12    
13    // 读入矩阵的每一个元素
14    for (int i = 1; i <= n; i++) {
15        for (int j = 1; j <= m; j++) {
16            scanf("%d", &a[i][j]);
17        }
18    }
19
20    // 枚举所有2×2子矩阵的左上角
21    for (int i = 1; i < n; i++) {        // i < n 保证 i+1 不越界
22        for (int j = 1; j < m; j++) {    // j < m 保证 j+1 不越界
23            // 检查对角线乘积是否相等
24            if (a[i][j] * a[i + 1][j + 1] == a[i + 1][j] * a[i][j + 1]) {
25                ans++;
26            }
27        }
28    }
29
30    // 输出答案
31    printf("%d\n", ans);
32    return 0;
33}

代码要点说明：

• 数组 a 的大小设置为 505，足够容纳题目范围内的最大矩阵。
• 下标从 1 开始使用，更直观地对应数学上的行列号。
• 外层循环条件为 i < n，内层为 j < m，自然避免了访问越界，同时也处理了行数或列数小于 2 的特殊情况（此时循环不执行，答案为 0）。
• 判断条件直接对比两个乘积，由于元素值范围较小（(-100 \le A_{i,j} \le 100)），乘积不会溢出 int 范围。
• 最终输出统计结果。

总结

本题的突破口在于理解“好的”子矩阵的定义，并将其转化为一个简单的等式判断。由于只需求解 (2 \times 2) 的固定尺寸子矩阵，完全可以通过暴力枚举在极短时间内得到结果。该解法思路清晰、实现简单，适合初学二维数组遍历和基本数学条件判断的同学。