Diffusion (multi-source search)

Xiaolan paints on an infinite special canvas .

This canvas can be seen as a grid , Each lattice can be represented by a two-dimensional integer coordinate .

Xiao Lan first made a few dots on the canvas ：(0, 0), (2020, 11), (11, 14), (2000, 2000)

Only these squares have black , The rest of the place is white .

Every minute , The black will spread a little bit . Concrete , If the inside of a grid is black , It's going to spread to 、 Next 、 Left 、 In the right four adjacent squares , Make these four squares black （ If it turns out to be black , It's still black ）.

Excuse me, , after 2020 Minutes later , How many squares on the canvas are black .
analysis ： Four points spread at the same time , Consider the problem of overlap , And the more points spread in the next second , The first thing I wrote was to search every point separately , If the first point spreads to the second point and has been marked , At the second point, you won't search , The result is wrong ;
So search from multiple sources at the same time , When there is a little overlap , The first source point shows that there is more time left , The range of subsequent diffusion is also the largest , Later, there was less time at the source , The diffusion range is certainly not as large as that of the first ;
Again, why not search widely ,2020 Nodes have high complexity , Long time , Guangsearch can save time through space

#include<bits/stdc++.h>
using namespace std;
int ans=4;
int book[9999][9999];
int nex[4][2]={
    0,1,0,-1,1,0,-1,0};
struct node
{
    
	int x,y,z;
}l,head;
queue <node> q;
void  bfs()
{
    
	while( !q.empty() )
	{
    
		head=q.front();
		q.pop();
		if(head.z>=2020)
		continue;
		for(int i=0;i<4;i++)
		{
    
			int tx=head.x+nex[i][0];
			int ty=head.y+nex[i][1];
			if(book[tx][ty]==0)
			{
    
				book[tx][ty]=1;
				ans++;
				l.x=tx;
				l.y=ty;
				l.z=head.z+1;
				q.push(l);
			}
		}
	}
}
int main()
{
    	
	book[3000][3000]=1;
	book[5020][3011]=1;
	book[3011][3014]=1;
	book[5000][5000]=1;
	l.x=3000;
	l.y=3000;
	l.z=0;
// q.push(l); 
 q.push({
    3000,3000,0});
 // It's OK to write like this , The queue has been specified as structure type in the front 
// bfs();
	
	l.x=5020;
	l.y=3011;
	l.z=0;
	q.push(l);	
// bfs();
	
	l.x=3011;
	l.y=3014;
	l.z=0;
	q.push(l);	
// bfs();

	l.x=5000;
	l.y=5000;
	l.z=0;
	q.push(l);	
	bfs();
	printf("%d\n",ans);
}