蓝桥杯-扩散

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)(0,0),(2020,11),(11,14),(2000,2000)。

只有这几个格子上有黑色，其它位置都是白色的。

每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。

请问，经过 20202020 分钟后，画布上有多少个格子是黑色的。

解题思路：

通过BFS模拟每分钟将每个点扩散，最后统计所有的点即可

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

#define ll long long
const ll maxn = 1e9 + 5;
set<pair<int, int>> a;
queue<pair<int, int>> b;

int main()
{
    b.push({0, 0});
    b.push({2020, 11});
    b.push({11, 14});
    b.push({2000, 2000});
    a.insert({0, 0});
    a.insert({2020, 11});
    a.insert({11, 14});
    a.insert({2000, 2000});
    int n = 2020;
    //模拟进行2020分钟
    while(n--)
    {
        //计算出当前有多少个点需要上下左右扩散
        ll m = b.size();
        while(m--)
        {
            //取出队头的点
            ll x = b.front().first, y = b.front().second;
            //判断在集合中该点是否已经被扩散（优化复杂度）
            if(!a.count({x+1, y}))
            {
                b.push({x+1, y});
                a.insert({x+1, y});
            }
            if(!a.count({x-1, y}))
            {
                b.push({x-1, y});
                a.insert({x-1, y});
            }
            if(!a.count({x, y+1}))
            {
                b.push({x, y+1});
                a.insert({x, y+1});
            }
            if(!a.count({x, y-1}))
            {
                b.push({x, y-1});
                a.insert({x, y-1});
            }
            //上下左右扩散后代表扩散完成，删除该点
            b.pop();
        }
    }
    //输出所有被扩散的点总个数（去重后）
    //答案20312088（要跑10分钟）
    cout << a.size();
    return 0;
}