题目描述
题目链接 https://www.lanqiao.cn/problems/1019/learning/
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (11, 14), (2000, 2000)(0,0),(2020,11),(11,14),(2000,2000)。
只有这几个格子上有黑色,其它位置都是白色的。
每过一分钟,黑色就会扩散一点。具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。
请问,经过 20202020 分钟后,画布上有多少个格子是黑色的。
算法
(bfs)
通过记录每个点被访问的时间戳,来判断是否是2020分内可以到达的点。
bfs 按层搜索。。。唉!
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x;
int y;
int t;
};
int vis[7000][7000];
int ne[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
queue<node> que;
void bfs(){
memset(vis,0,sizeof(vis));
int n = 2100;
node p,q;
p.t = 0, p.x = n, p.y = n;
que.push(p), vis[p.x][p.y]=1;
p.t = 0, p.x = n + 2020, p.y = n + 11;
que.push(p), vis[p.x][p.y]=1;
p.t = 0, p.x = n + 11, p.y = n + 14;
que.push(p), vis[p.x][p.y]=1;
p.t = 0, p.x = n + 2000, p.y = n + 2000;
que.push(p), vis[p.x][p.y]=1;
long long ans = 4;
while(!que.empty()){
p = que.front();
que.pop();
for(int i=0;i<4;i++){
q.x = p.x + ne[i][0];
q.y = p.y + ne[i][1];
q.t = p.t + 1;
if(vis[q.x][q.y]==0 && q.t<=2020){
vis[q.x][q.y]=1;
ans++;
que.push(q);
}
}
}
cout<<ans<<endl;
}
int main()
{
bfs();
//cout<<20312088<<endl;
return 0;
}