题解 | 病菌感染

·题意

·给定一n*n矩阵,初始有m个方格被感染，当一个方格相邻的方格中有两个及以上的方格被感染时，该方格会感染；

n <= 1000, m < n;

·分析

·可发现,最效率感染情况为，有感染方格对角相邻时，感染方格可扩散，如图:

·所以，在最优感染的情况下，即对角线，感染全部结点都至少需要有n个结点初始感染

·但是 m < n，所以无论如何，都不可能全感染!

·所以直接输出NO 就AC了

·复杂度

都是O(1)

·完整代码

#include <iostream>

using namespace std;
int main()
{
    puts("NO");
    return 0;
}

不知道题目有没有改过，但是现在的题确实只需要输出一个NO qwq;