一、核心知识点

1. 二维数组与下标

二维数组可以看成一张由行和列组成的表格。a[i][j] 表示第 $i$ 行、第 $j$ 列的元素。

本节统一从下标 $1$ 开始存储：

int a[105][105];

for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		cin>>a[i][j];
	}
}

第一层循环枚举行，第二层循环枚举列。若题目给出的最大行数、列数都是 $100$，数组应当开到 105 左右，为边界位置留出空间。

2. 按行遍历与按列遍历

按行处理第 $i$ 行：

for(int j=1;j<=m;j++){
	// 处理 a[i][j]
}

按列处理第 $j$ 列：

for(int i=1;i<=n;i++){
	// 处理 a[i][j]
}

读题时要先分清 $n$ 表示行数还是列数，输出时也要按照题目要求的行列顺序遍历。

3. 相邻位置与边界判断

一个位置 $(i,j)$ 的上、下、左、右分别是：

• $(i-1,j)$
• $(i+1,j)$
• $(i,j-1)$
• $(i,j+1)$

如果还包含斜对角方向，就一共有八个相邻位置。访问相邻位置前必须判断新位置是否仍在矩阵中：

if(x>=1&&x<=n&&y>=1&&y<=m){
	// (x,y) 没有越界
}

当方向固定时，可以使用方向数组统一枚举，减少重复代码：

int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

4. 原数组与结果数组

如果所有位置的新值都必须根据“变化前”的矩阵计算，就不能一边计算一边修改原数组。否则后面的计算可能读到已经改变的值。

正确方法是使用两个数组：

• a 保存本轮开始时的数据；
• b 保存本轮计算出的新数据；
• 本轮全部计算结束后，再把 b 复制回 a。

这种方法称为双数组模拟，常用于图像处理、生命游戏和扩散过程。

5. 计数、比例与保留小数

二维数组中的统计通常分为三步：遍历所有位置、判断是否满足条件、更新计数器。

计算百分比时，要保证除法是实数除法：

double ans=cnt*100.0/(n*m);
printf("%.2f\n",ans);

其中 100.0 是实数，可以避免整数除法丢失小数部分。

6. 奇偶性

判断一个整数是否为偶数，可以使用：

if(sum%2==0){
	// sum 是偶数
}

把二进制矩阵中的一个元素由 $0$ 变成 $1$，或者由 $1$ 变成 $0$，会同时改变该元素所在行与所在列的奇偶性。这一性质可以帮助我们直接确定需要修改的位置。

---

二、矩阵乘法

题目编号： P2706
docId： 5485

题意概括

给定一个 $n\times m$ 的矩阵 $A$ 和一个 $m\times k$ 的矩阵 $B$，计算它们的乘积矩阵 $C$。

结果矩阵有 $n$ 行 $k$ 列，其中：

$$C[i][j]=\sum_{t=1}^{m}A[i][t]\times B[t][j]$$

思路分析

计算 c[i][j] 时，要把矩阵 $A$ 的第 $i$ 行与矩阵 $B$ 的第 $j$ 列对应相乘后求和。

使用三层循环：

1. 枚举结果矩阵的行 i；
2. 枚举结果矩阵的列 j；
3. 枚举相乘位置 t，累加 a[i][t]*b[t][j]。

时间复杂度为 $O(nmk)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,k;
int a[N][N],b[N][N],c[N][N];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=k;j++){
			cin>>b[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			// A 的第 i 行与 B 的第 j 列对应相乘并求和
			for(int t=1;t<=m;t++){
				c[i][j]+=a[i][t]*b[t][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(j>1) cout<<" ";
			cout<<c[i][j];
		}
		cout<<"\n";
	}
	return 0;
}

---

三、扫雷

题目编号： P1573
docId： 5490

题意概括

给定一个 $n\times m$ 的雷区，* 表示地雷，? 表示空地。地雷位置仍输出 *，空地位置输出周围八个相邻格子中的地雷数量。

思路分析

逐个遍历矩阵中的格子：

• 当前格是 *，直接输出；
• 当前格是 ?，枚举周围八个方向；
• 相邻位置没有越界且为 * 时，计数加一。

每个格子最多检查八次，时间复杂度为 $O(nm)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
char a[N][N];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*'){
				cout<<'*';
				continue;
			}
			int cnt=0;
			// 枚举当前格周围的八个位置
			for(int d=0;d<8;d++){
				int x=i+dx[d];
				int y=j+dy[d];
				if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='*'){
					cnt++;
				}
			}
			cout<<cnt;
		}
		cout<<"\n";
	}
	return 0;
}

---

四、图像模糊处理

题目编号： P2708
docId： 5487

题意概括

给定一幅由灰度值组成的图像。最外层像素保持不变；内部像素的新灰度值等于它自己及上、下、左、右五个位置原灰度值的平均数，并四舍五入到最接近的整数。

思路分析

所有新灰度值都要根据原图计算，因此使用数组 a 保存原图，数组 b 保存处理结果。

先把所有位置复制到 b，这样边界自然保持不变。然后只计算第 $2$ 至第 $n-1$ 行、第 $2$ 至第 $m-1$ 列。

五个灰度值均为非负整数，设总和为 sum，四舍五入后的平均数可以写成 (sum+2)/5。

时间复杂度为 $O(nm)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int a[N][N],b[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			b[i][j]=a[i][j];
		}
	}
	for(int i=2;i<n;i++){
		for(int j=2;j<m;j++){
			int sum=a[i][j]+a[i-1][j]+a[i+1][j]
				+a[i][j-1]+a[i][j+1];
			// 非负整数除以 5，先加 2 可以完成四舍五入
			b[i][j]=(sum+2)/5;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j>1) cout<<" ";
			cout<<b[i][j];
		}
		cout<<"\n";
	}
	return 0;
}

---

五、图像相似度

题目编号： P2704
docId： 5484

题意概括

给定两幅大小相同的黑白图像。统计相同位置颜色相同的像素数量，并计算它占全部像素的百分比，结果保留两位小数。

思路分析

分别读入两个矩阵，再遍历所有位置。如果 a[i][j]==b[i][j]，说明该位置相同，计数器 cnt 加一。

总像素数为 $n\times m$，所以相似度为：

$$\frac{cnt}{n\times m}\times 100\%$$

计算时使用 100.0，让整个算式按照实数除法计算。

时间复杂度为 $O(nm)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int a[N][N],b[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>b[i][j];
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==b[i][j]) cnt++;
		}
	}
	// 乘 100.0，避免使用整数除法
	double ans=cnt*100.0/(n*m);
	printf("%.2f\n",ans);
	return 0;
}

---

六、错误探测

题目编号： P3594
docId： 5488

题意概括

给定一个只含 $0$ 和 $1$ 的 $n\times n$ 矩阵。合法矩阵要求每一行、每一列的 $1$ 的数量都是偶数。

• 已经合法，输出 OK；
• 改变一个元素后可以合法，输出这个元素的行号和列号；
• 否则输出 Corrupt。

思路分析

分别统计每一行与每一列的元素和，再记录有多少行、多少列的和为奇数。

改变位置 $(x,y)$ 的一个元素，只会改变第 $x$ 行和第 $y$ 列的奇偶性。因此：

• 没有奇数行，也没有奇数列，矩阵已经合法；
• 恰好有一个奇数行和一个奇数列，修改它们的交点即可；
• 其他情况无法只修改一个元素解决。

不需要枚举每个位置尝试修改，时间复杂度为 $O(n^2)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n;
int a[N][N],row[N],col[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			row[i]+=a[i][j];
			col[j]+=a[i][j];
		}
	}
	int rowCnt=0,colCnt=0;
	int badRow=0,badCol=0;
	for(int i=1;i<=n;i++){
		if(row[i]%2==1){
			rowCnt++;
			badRow=i;
		}
		if(col[i]%2==1){
			colCnt++;
			badCol=i;
		}
	}
	if(rowCnt==0&&colCnt==0){
		cout<<"OK\n";
	}else if(rowCnt==1&&colCnt==1){
		// 修改唯一奇数行与唯一奇数列的交点
		cout<<badRow<<" "<<badCol<<"\n";
	}else{
		cout<<"Corrupt\n";
	}
	return 0;
}

---

七、细菌的繁殖与扩散

题目编号： P3596
docId： 5489

题意概括

在一个 $9\times 9$ 的培养皿中，最初只有中心位置 $(5,5)$ 有 $m$ 个细菌。每个细菌一天后产生十个后代：两个留在原位置，其余八个分别进入周围八个相邻位置。求经过 $n$ 天后的细菌分布。

思路分析

每天的所有新细菌都应由当天开始时的分布产生，因此使用双数组模拟：

1. a 保存今天开始时的细菌数量；
2. 清空 b，用于统计下一天；
3. 对每个位置，把 2*a[i][j] 加到原位置，把 a[i][j] 分别加到周围八格；
4. 一天结束后，把 b 复制回 a。

因为最初位于中心且最多扩散四天，细菌不会越过 $9\times9$ 培养皿。代码仍保留边界判断，使每次访问都清晰、安全。

时间复杂度为 $O(n\times 9\times 9)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int m,n;
int a[N][N],b[N][N];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int main(){
	cin>>m>>n;
	a[5][5]=m;
	for(int day=1;day<=n;day++){
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				b[i][j]=0;
			}
		}
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				// 两个后代留在原来的位置
				b[i][j]+=a[i][j]*2;
				// 其余八个后代分别扩散到周围八格
				for(int d=0;d<8;d++){
					int x=i+dx[d];
					int y=j+dy[d];
					if(x>=1&&x<=9&&y>=1&&y<=9){
						b[x][y]+=a[i][j];
					}
				}
			}
		}
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				a[i][j]=b[i][j];
			}
		}
	}
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(j>1) cout<<" ";
			cout<<a[i][j];
		}
		cout<<"\n";
	}
	return 0;
}

---

八、复习检查清单

• 能否准确区分行数、列数以及 a[i][j] 中两个下标的含义？
• 能否用两层循环完成二维数组的输入、遍历和输出？
• 访问相邻位置前，是否检查了行、列边界？
• 计算新一轮状态时，是否需要使用另一个数组保存结果？
• 计算百分比时，是否避免了整数除法？
• 修改一个矩阵元素时，能否判断它会影响哪一行、哪一列？
• 输出矩阵时，空格和换行是否符合题目要求？