【扩散——BFS】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int t = 2020, off = 2020;
#define x first
#define y second
typedef pair<int, int> PII;
int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
int dist[6080][6080]; // 0映射到2020，2020映射到4040int bfs()
{queue<PII> q;q.push({0 + off, 0 + off});q.push({2020 + off, 11 + off});q.push({11 + off, 14 + off});q.push({2000 + off, 2000 + off});dist[0 + off][0 + off] = dist[2020 + off][11 + off] = dist[11 + off][14 + off] = dist[2000 + off][2000 + off] = 1;while (q.size()){int x = q.front().x, y = q.front().y;q.pop();if (dist[x][y] >= t + 1)continue;for (int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i];if (dist[nx][ny])continue;dist[nx][ny] = dist[x][y] + 1;q.push({nx, ny});}}int ans = 0;for (int i = 0; i <= 6070; i++){for (int j = 0; j <= 6070; j++){if (dist[i][j])ans++;}}return ans;
}
int main()
{cout << bfs();return 0;
}