首页 > 试题广场 >

病菌感染

[编程题]病菌感染
铁子和顺溜上生物课的时候不小心将几滴超级病菌滴到了培养皿上,这可急坏了他们。
培养皿可以被看成一个n*n的方格,最初病菌滴在了这n*n的格子中的某些格子,病菌的传染方式是这样的,如果一个方格与两个或多个被感染的方格相邻(两个方格相邻当且仅当它们只有一条公共边),
那么它就会被感染。现在铁子和顺溜想知道,最终所有的方格会不会都被感染。

输入描述:
第一行两个整数n,m。n表示方格的规格,m表示最初病菌所在的格子数。(1 ≤ n ≤ 1000, 0 < m < n)。
接下来m行每行两个整数xi,yi表示第xi行的第yi个格子有病菌。
数据保证不会有两个病菌初始时在同一个格子。


输出描述:
如果最终所有的方格都会被感染,输出 YES。
否则输出 NO。
示例1

输入

3 2
1 2
2 2

输出

NO
头像 小琢卷不动
发表于 2021-11-23 20:42:31
考虑类似 bfs 的过程,通过一个队列去扩展我们的答案就好。 一个格子被感染,可以影响到它周围的 444 个格子,而一个格子周边一旦存在 ≥2\ge2≥2 个格子被感染那么它也会被感染,这个直接建图,类似一个拓扑排序,入度 =0=0=0 就拓扑过去就好了。 时间复杂度 O(nm)O(nm)O(nm) 展开全文
头像 行大道
发表于 2023-03-19 09:25:12
#include<bits/stdc++.h> using namespace std; int a[1001][1001],n,m,s,f=1; int main() {     cin>>n>>m;     for 展开全文
头像 牛客532105025号
发表于 2023-08-30 19:55:33
简单的多路广搜。 将最初病菌放入队列,之后依次出列,判断其向外蔓延的格子是否可以被病菌覆盖,可以被覆盖将其放入队列,否则不做操作。 代码: void solve() { int n,m; cin>>n>>m; // 按 从 0 到 n-1 进行建图 v 展开全文

问题信息

难度:
0条回答 10浏览

热门推荐

通过挑战的用户

查看代码
病菌感染