week3-[二维数组]小方块

week3-[二维数组]小方块

题目描述

如果四个数 $a,b,c,d$ 可以分成两组，每组两个数，满足每组里面的两个数一样，那么称这四个数是好的。

比如，$2,5,2,5$ 是好的，因它满足两组：$2$ 与 $2$ 两个数一样，$5$ 与 $5$ 两个数一样。

给定一个 $n$ 行 $m$ 列的二维数组 $a_{i,j}$，有多少对 $x,y$ 满足 $a_{x,y},a_{x+1,y},a_{x,y+1},a_{x+1,y+1}$ 是好的？

输入格式

输入共 $n+1$ 行。

第 $1$ 行 $2$ 个正整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个用空格隔开的正整数 $a_{i,j}$。

输出格式

输出共 $1$ 行 $1$ 个整数表示答案。

样例 #1

样例输入 #1

2 4
1 2 3 2
2 3 2 3

样例输出 #1

2

提示

样例解释 $1$

$x=1,y=1$：四个数分别为 $1,2,2,3$，不是好的。

$x=1,y=2$：四个数分别为 $2,3,3,2$，是好的。

$x=1,y=3$：四个数分别为 $3,2,2,3$，是好的。

不能有 $x=2$ 或者 $y=4$，因为这样的话就没有四个数了。

数据范围

对于所有数据，$1\le n,m,a_{i,j}\le 100$。

这题是典型的 2×2 小方块匹配问题。核心是判断 四个数是否能分成两组，每组两个数相等。

---

🔎 分析

1️⃣ 判断“好”的条件

设四个数为 a,b,c,da, b, c, da,b,c,d，它们是“好”的有几种可能：

1. 两两相等：
   • (a == b && c == d)
   • (a == c && b == d)
   • (a == d && b == c)

如果满足其中任意一种，就是好的。

注意顺序不重要，四个数中每组两个相等即可。

---

2️⃣ 枚举所有 2×2 方块

• 遍历 i = 0..n-2
• 遍历 j = 0..m-2
• 四个数：a[i][j], a[i+1][j], a[i][j+1], a[i+1][j+1]
• 判断是否好 → 累加计数

---

🖥️ C++ 实现

#include <bits/stdc++.h>
using namespace std;int main() {int n,m;cin >> n >> m;vector<vector<int>> a(n, vector<int>(m));for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin >> a[i][j];int cnt = 0;for(int i=0;i<n-1;i++){for(int j=0;j<m-1;j++){int x1 = a[i][j], x2 = a[i+1][j], x3 = a[i][j+1], x4 = a[i+1][j+1];if ((x1==x2 && x3==x4) ||(x1==x3 && x2==x4) ||(x1==x4 && x2==x3)) {cnt++;}}}cout << cnt << endl;return 0;
}