题面
【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。 只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色 （如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路
BFS。从起始给定的四个点出发，广度遍历每个点的四个方向，没走到一个没有被染色的格子则计数器加一。注意，由于题目给的画布大小为无限大，所以，其可以往横纵坐标为负的方向扩散，则在代码中应该将起始坐标进行偏移，偏移量设为大于2020的就可以，本人设为3000。
答案：20312088
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int M = 8000;
bool g[M][M];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int bfs() {
int res = 4;
int base = 3000;
queue<PII> q;
//起点
PII st[4] = {{0, 0},
{2020, 11},
{11, 14},
{2000, 2000}};
for (int i = 0; i < 4; i++) {
st[i].x += base;
st[i].y += base;
q.push(st[i]);
g[st[i].x][st[i].y] = true;
}
int t = 2020;
while (t--) {
int size = q.size();
while (size--) {
PII now = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int ti = now.x + dir[d][0], tj = now.y + dir[d][1];
// if (ti < 0 || ti >= M || tj < 0 || tj >= M) continue; //可以不写，保证不会超过边界
if (g[ti][tj]) continue;
res++;
g[ti][tj] = true;
q.push({ti, tj});
}
}
}
return res;
}
int main() {
cout << bfs() << endl;
return 0;
}
| 标题： | 2020第十一届蓝桥杯国赛-B扩散 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/105 |
| 更新： | 2022-09-18 22:39:14 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |