【問題描述】
小藍(lán)在一張無限大的特殊畫布上作畫。
這張畫布可以看成一個(gè)方格圖，每個(gè)格子可以用一個(gè)二維的整數(shù)坐標(biāo)表示。
小藍(lán)在畫布上首先點(diǎn)了一下幾個(gè)點(diǎn)：(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有這幾個(gè)格子上有黑色，其它位置都是白色的。
每過一分鐘，黑色就會擴(kuò)散一點(diǎn)。具體的，如果一個(gè)格子里面是黑色，它
就會擴(kuò)散到上、下、左、右四個(gè)相鄰的格子中，使得這四個(gè)格子也變成黑色
（如果原來就是黑色，則還是黑色）。
請問，經(jīng)過 2020 分鐘后，畫布上有多少個(gè)格子是黑色的。

代碼如下:

#include <iostream> #include <queue> using namespace std; const int N = 10010; bool vis[N][N]; typedef long long LL; LL ans = 0;int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};struct node {int x;int y;int p; };void bfs() {queue<node>q;vis[0 + 3000][0 + 3000] = true;//相對位置不變結(jié)果不變 ，不加數(shù)組會越界 //這里如果不是加3000，是加2000也會越界，//所以我們還是盡量讓它移動到比較中間的位置vis[2020 + 3000][11 + 3000] = true;vis[11 + 3000][14 + 3000] = true;vis[2000 + 3000][2000 + 3000] = true;q.push({0 + 3000, 0 + 3000, 0});q.push({2020 + 3000, 11 + 3000, 0});q.push({11 + 3000, 14 + 3000, 0});q.push({2000 + 3000, 2000 + 3000, 0});ans = 4;//最開始有4個(gè)點(diǎn)while (q.size()) {node t = q.front();q.pop();if (t.p == 2020)continue;for (int i = 0; i < 4; i++) {int xx = t.x + dx[i], yy = t.y + dy[i];if (!vis[xx][yy]) {vis[xx][yy] = true;ans++;q.push({xx, yy, t.p + 1});}}} }int main() {bfs();cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的十一届蓝桥杯国赛 扩散-多源bfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。