大意：有一个画家，画了n栋摩天大楼。（实际上只有远远望去的轮廓）。每栋楼都是一个矩形，有些矩形是重叠在一起的。所有的矩形的底边都在一条直线上。很不幸，画被烧毁了。但是记得每个矩形的位置和高度，现在请你复原这幅画，并求出矩形的轮廓线的周长（不包含底边）。
思路：在覆盖了图片之后，用一遍BFS解决问题(我之前写的时候本以为是要把整个矩形全部覆盖，后来发现不需要，但是之前写的树状数组懒得改了……)
代码：
#include#include #define MAXN 1006int c[MAXN][MAXN], h[MAXN][MAXN], n, M, N, l, r, NN = 0x3f3f3f3f;bool vis[MAXN][MAXN];struct P{ int a, b; P(){} P(int q, int w){a = q; b = w;}}q[MAXN*MAXN];void Upd(int a[], int x, int v){ for(; x <= 1000; x += (x&(-x))) a[x] += v;}int Q(int a[], int x){ int ans = 0; for(; x > 0; x -= (x&(-x))) ans += a[x]; return ans;}char mp[MAXN][MAXN], ans[MAXN][MAXN];int num;int main(){ int t1, t2, t3; scanf("%d\n", &n); for(int i = 1; i <= n; i ++) { scanf("%d%d%d", &t1, &t2, &t3); if(M < t2-1) M = t2-1; if(N < t3) N = t3; if(NN > t1) NN = t1; Upd(h[t3], t1, 1); Upd(h[t3], t2, -1); Upd(c[t1], 1, 1); Upd(c[t1], t3+1, -1); Upd(c[t2-1], 1, 1); Upd(c[t2-1], t3+1, -1); } for(int i = 1; i <= N; i ++) for(int j = 1; j <= M; j ++) if(Q(c[j], i) || Q(h[i], j)) mp[i][j] = '#'; q[++r] = P(N + 1, 1); vis[N+1][1] = 1; while(l < r) { P t = q[++l]; if(mp[t.a][t.b-1] == '#') ans[t.a][t.b-1] = '#', num++; else if(t.a>0&&t.b-1>=0 && !vis[t.a][t.b-1]) {q[++r] = P(t.a, t.b-1);vis[t.a][t.b-1] = 1;} if(mp[t.a-1][t.b] == '#') ans[t.a-1][t.b] = '#', num++; else if(t.a>1&&t.b>=0 && !vis[t.a-1][t.b]) {q[++r] = P(t.a-1, t.b);vis[t.a-1][t.b] = 1;} if(mp[t.a][t.b+1] == '#') ans[t.a][t.b+1] = '#', num++; else if(t.a>0&&t.b>=0&&t.b<=M && !vis[t.a][t.b+1]) {q[++r] = P(t.a, t.b+1);vis[t.a][t.b+1] = 1;} if(mp[t.a-1][t.b+1] == '#') ans[t.a-1][t.b+1] = '#'; if(mp[t.a-1][t.b-1] == '#') ans[t.a-1][t.b-1] = '#'; } printf("%d\n", num); for(int i = N; i > 0; i --) { for(int j = NN; j <= M; j ++) if(ans[i][j] == '#') putchar('#'); else putchar('.'); putchar('\n'); } for(int i = NN; i <= M; i ++) putchar('*'); putchar('\n'); return 0;}