2D Conveyor Belt (USACO Silver 2024 December)
两种情况下方块会不可用：形成环的传送带上的点是不可用的，环内部包围的点也是不可用的。我们发现求不可用点不太方便，正难则反，想想反过来求可用的点：从边界开始DFS，沿传送带反方向，或者到达？方块这样的遍历，所有可到达的方块都可用。DFS一次，可以得到在一种传送带配置的情况下的可用/不可用方块状态和数量。
如果我们每次加一个传送带做一遍DFS，就必然TLE了。我们发现DFS复杂度高的原因是每次做很多重复的遍历工作，所以我们考虑再次逆向求解，直接先求最终状态下的可用方块集合，然后一个个删除传送带，再从删除传送带的方块开始做DFS（本质上是个delta的计算，每次只访问新的可用的方块），这样就保证每个方块最多访问一次，不会多次重复访问，就可以地解决问题了。
所以两个要点：一是要求可用方块，而不是不可用方块；二是用反向去掉传送带的方式，时间逆序地求。
#include <bits/stdc++.h>
using namespace std;
int n, q;
char s[1005][1005];
int r[200005], c[200005];
char d[200005];
bool ok[1005][1005];
int cnt;
int ans[200005];
bool bound(int r, int c) {
return r >= 1 && r <= n && c >= 1 && c <= n;
}
void dfs(int r, int c) {
if (ok[r][c]) return;
ok[r][c] = 1;
cnt++;
// follow the reverse direction
if (bound(r-1, c) && (s[r-1][c] == 'D' || s[r-1][c] == 0)) dfs(r-1, c);
if (bound(r, c-1) && (s[r][c-1] == 'R' || s[r][c-1] == 0)) dfs(r, c-1);
if (bound(r+1, c) && (s[r+1][c] == 'U' || s[r+1][c] == 0)) dfs(r+1, c);
if (bound(r, c+1) && (s[r][c+1] == 'L' || s[r][c+1] == 0)) dfs(r, c+1);
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= q; i++) {
scanf("%d %d %c", &r[i], &c[i], &d[i]);
s[r[i]][c[i]] = d[i];
}
for (int i = 1; i <= n; i++) {
if (s[1][i] == 'U' || s[1][i] == 0) dfs(1, i);
if (s[i][1] == 'L' || s[i][1] == 0) dfs(i, 1);
if (s[n][i] == 'D' || s[n][i] == 0) dfs(n, i);
if (s[i][n] == 'R' || s[i][n] == 0) dfs(i, n);
}
ans[q] = n*n - cnt;
for (int i = q; i >= 1; i--) {
int rr = r[i], cc = c[i];
s[rr][cc] = 0;
if (!ok[rr][cc]) {
if (ok[rr+1][cc] || ok[rr-1][cc] || // neighbor is valid
ok[rr][cc+1] || ok[rr][cc-1] ||
rr == 1 || rr == n || cc == 1 || cc == n) // on border
{
dfs(rr, cc);
}
}
ans[i-1] = n*n - cnt;
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}