题解 | #病菌感染#

考虑类似 bfs 的过程，通过一个队列去扩展我们的答案就好。

一个格子被感染，可以影响到它周围的 $44$ 个格子，而一个格子周边一旦存在 $\ge 2\backslash ge2$ 个格子被感染那么它也会被感染，这个直接建图，类似一个拓扑排序，入度 $=0=0$ 就拓扑过去就好了。

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

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e3 + 5;
int n, m, q[N * N], du[N * N];
int node(int x, int y){
    return (x - 1) * n + y;
}
int dx[] = {0, 0, 0, 0};
bool vis[N * N];
int main(){
    n = init(), m = init();
    for (int i = 1; i <= m; ++i) {
        int x = init(), y = init();
        q[++q[0]] = node(x, y);
    }
    dx[0] = -n, dx[2] = n;
    dx[1] = -1, dx[3] = 1;
    int nxt = 1;
    while (nxt <= q[0]) {
        int u = q[nxt++];
        for (int k = 0; k < 4; ++k) {
            int v = u + dx[k];
            if (v < 1 || v > n * n) continue;
            if (!vis[v]) {
                ++du[v];
                if (du[v] >= 2) {
                    q[++q[0]] = v;
                    vis[v] = 1;
                }
            }
        }
    }
    puts(q[0] == n * n ? "YES" : "NO");
}