官方题解

【算法分析】

定义整型数组 $a$，下标从 $1$ 开始存，防止越界。未被感染的置为 $0$，已被感染的置为 $1$，空的房子置为 $-1$。

$m - 1$ 天感染，遍历数组 $a$，为防止在这一轮中，感染后的人感染下一轮的人，将上一轮已被感染的人的邻居置为$2$。然后再次遍历数组 $a$， $a[i][j]$ 等于 $2$ 则置为 $1$。

$m - 1$ 天感染结束后，统计被感染人数，并输出。

【参考代码】

#include<iostream>
using namespace std;

const int N = 110;
int a[N][N];

int main() {
	int n, m, sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char s;
			cin >> s;
			if (s == '.') a[i][j] = 0; //未被感染的 
			if (s == '@') a[i][j] = 1; //已被感染的 
			if (s == '#') a[i][j] = -1;//空的 
		}
	}
	cin >> m;
	while (m > 1) { //m-1天 
		m--;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (a[i][j] == 1) { //防止在这一轮中，感染后的人感染下一轮的人，将邻居置为2 
					if (a[i + 1][j] == 0) a[i + 1][j] = 2;
					if (a[i - 1][j] == 0) a[i - 1][j] = 2;
					if (a[i][j + 1] == 0) a[i][j + 1] = 2;
					if (a[i][j - 1] == 0) a[i][j - 1] = 2;
				}
			}
		}
		for (int i = 1; i <= n; i++) {  //这一轮被感染的人置为1 
			for (int j = 1; j <= n; j++) {
				if (a[i][j] == 2) a[i][j] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 1) sum++;
		}
	}
	cout << sum;
	return 0;
}

【时间复杂度】

$O(mn^2)$

【预计得分】

$100pts$