【扩散——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映射到4040

int 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;
}