Replication (USACO Gold 2020 Dec)

因为 $N$ 是 $1000$ ，所以我们需要 $\mathcal{O}(N^2)$ 的算法， $N^3$ 不行，此题的关键就是怎样尽量降低复杂度，避免出现 $N^3$ 。

机器人复制之后就会变成“群”，形状是这样：

.....    .....    ..X..
.....    ..X..    .XXX.
..X.. -> .XXX. -> XXXXX
.....    ..X..    .XXX.
.....    .....    ..X..

就是一个菱形。所以比较自然可以想到，我们可以简化机器人的表达方式，用一个tuple表示一群机器人： $(r,c,t)$ 三元组来表示 $t$ 时间在坐标 $(r,c)$ 处的一群机器人，因为时间决定了机器人群的大小，所以不需要再存储大小了。

当整群机器人移动的时候，我们需要检测是否碰上墙，以及访问了哪些之前没有到过的位置。naive来看这两个操作都是 $N^2$ 复杂度，是不行的。但观察可以发现，如果有碰撞，可以证明就是发生在这个菱形的边界上，访问没访问过的位置也会发生在这个边界上，而边界的长度是 $N$ 的复杂度。所以通过小心处理碰撞，和mark哪些节点访问过，就能保证这里不超时。

同时，我们可以证明，当有多个群访问同一个位置时，我们只需要记录最早到的（也就是最小的群），这样使得我们要处理的节点数就是 $N^2$ 。

然后使用简单的BFS就可以完成整个题目，复杂度 $\mathcal{O}(N^2)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, d;       // n <= 1000
char s[1005][1005];
struct G {      // a group
    int r,c,t;  // t/d决定了group的大小
};
queue<G> q;
bool on[1005][1005];
bool vis[1005][1005];
int ans;
 
bool inbound(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}
 
bool valid(int r, int c, int sz) {
    bool ok = true;
    auto check = [&](int R, int C) {
        if (!inbound(R,C) || s[R][C]=='#')
            ok = false;
    };
    for (int i = 0; i < sz; i++) {
        check(r+i,c+sz-1-i);
        check(r-i,c-(sz-1-i));
        check(r+(sz-1-i),c-i);
        check(r-(sz-1-i),c+i);
    }
    return ok;
}
 
void mark(int r, int c, int sz) {
    auto markit = [](int R, int C) {
        if (!on[R][C]) {
            on[R][C] = 1;
            ans++;
        }
    };
    for (int i = 0; i < sz; i++) {
        markit(r+i,c+sz-1-i);
        markit(r-i,c-(sz-1-i));
        markit(r+(sz-1-i),c-i);
        markit(r-(sz-1-i),c+i);
    }
}
 
int main() {
    scanf("%d %d", &n, &d);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; j++)
            if (s[i][j] == 'S') {
                q.push({i,j,0});
                on[i][j] = true;
                ans++;
            }
    }
    while (!q.empty()) {
        G g = q.front();
        q.pop();
        if (vis[g.r][g.c]) continue;
        vis[g.r][g.c] = true;
        bool expand = g.t > 0 && g.t % d == 0;
        int sz = g.t / d + 1;
        if (expand) {
            if (!valid(g.r, g.c, sz-1)) continue;
            mark(g.r, g.c, sz-1);
        }
        bool ok = valid(g.r, g.c, sz);
        if (!ok) continue;
 
        mark(g.r, g.c, sz);     // mark on tiles
        q.push({g.r,g.c+1,g.t+1});
        q.push({g.r,g.c-1,g.t+1});
        q.push({g.r+1,g.c,g.t+1});
        q.push({g.r-1,g.c,g.t+1});
    }
    printf("%d", ans);
    return 0;
}