正经题解｜腐烂的橘子

【算法分析】

从所有为 $2$ 的位置开始广搜，只会将好的橘子（值为 $1$）感染，在每次放进队列的同时将值设为 $1$，以免重复访问。在最后的时候遍历一遍数组，如果还有新鲜的橘子，则输出 $-1$。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

int a[1009][1009];
struct node {
	int x, y, step;
}l,r;
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
int main() {
	int n, m;
	cin >> n >> m;
	queue<node> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 2) q.push({ i,j,0 });
		}
	}
	int ans = 0;
	while (q.size()) {
		r = q.front();
		q.pop();
		ans = max(ans, r.step);
		for (int i = 0; i < 4; i++) {
			l.x = r.x + dir[i][0], l.y = r.y + dir[i][1], l.step = r.step + 1;
			if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && a[l.x][l.y] == 1) {
				a[l.x][l.y] = 2;
				q.push(l);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 1) {
				ans = -1;
			}
		}
	}
	cout << ans;
	return 0;
}

【时间复杂度】

$O(n*m)$

【预计得分】

$100pts$