题目描述
给定一个二维平面和一些栅栏，求其中包含点 (0,0) 的封闭图形面积。n,m<=1000 。
Solution:
模型转化 。首先考虑把横纵坐标离散化，将二维平面转化成网格图。
显然总面积可以由若干矩形拼成，所以只要 BFS 求出哪些点可达。对于点 (i,j) 可达，面积为 (X[i+1]-X[i])*(Y[j+1]-Y[j]) 。
trick1 ：将左边界设为 -1.1e9 ，右边界设为 1.1e9 。trick2 ：以横栅栏为例，不难发现对于 在栅栏上的点 ，不能向上走； 在栅栏上一格的点，不能向下走，但可以两种情况都可以沿着左右走 。
下图表示了 (0,0) 可行的路径。
不难发现黄色节点不没有遍历到。这是一个很棘手的问题。
trick3 ：考虑将栅栏设置为 左闭右开 。如此可以遍历到黄色节点。
因为题目给定了 (0,0) 合法，可以考虑将 (0,0) 作为起点。如果遍历到了边界的点，则输出 -1 。
trick4 ：用 Z[x][y] 来状压 (x,y) 的上下左右 4 个方向 。
时间复杂度 O(nm) 。
话说这道题因为数组开小等问题 wa 飞了，下次应该避免这种情况。
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int mx=3005;
//注意要开三倍空间
//Task : Atcoder abc
//Author : cqbzly
//思路：离散化 + 搜索
//1. 坐标离散化
//2. 建边
//3. 跑搜索
int n,m;
int A[mx],B[mx],C[mx],D[mx],E[mx],F[mx];
int X[mx],Y[mx],XC,YC,Z[mx][mx],K[mx][mx];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
queue<pair<int,int> > Q;
int getx(int x) {
return lower_bound(X,X+XC,x)-X;
}
int gety(int x) {
return lower_bound(Y,Y+YC,x)-Y;
}
int main() {
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>A[i]>>B[i]>>C[i];
X[XC++]=A[i];
X[XC++]=B[i];
Y[YC++]=C[i];
}
for(int i=1;i<=m;i++) {
cin>>D[i]>>E[i]>>F[i];
X[XC++]=D[i];
Y[YC++]=E[i];
Y[YC++]=F[i];
}
X[XC++]=-1.1e9;
X[XC++]=0;
X[XC++]=1.1e9;
Y[YC++]=-1.1e9;
Y[YC++]=0;
Y[YC++]=1.1e9;
sort(X,X+XC),sort(Y,Y+YC);
XC=unique(X,X+XC)-X-1,YC=unique(Y,Y+YC)-Y-1;
for(int i=1;i<=n;i++) {
A[i]=getx(A[i]);
B[i]=getx(B[i]);
C[i]=gety(C[i]);
for(int j=A[i];j<B[i];j++) {
Z[j][C[i]-1]|=1<<0;
Z[j][C[i]]|=1<<2;
}
}
for(int i=1;i<=m;i++) {
D[i]=getx(D[i]);
E[i]=gety(E[i]);
F[i]=gety(F[i]);
for(int j=E[i];j<F[i];j++) {
Z[D[i]-1][j]|=1<<1;
Z[D[i]][j]|=1<<3;
}
}
int sx=getx(0),sy=gety(0);
Q.push(mp(sx,sy)),K[sx][sy]=1;
while(Q.size()) {
int x=Q.front().first,y=Q.front().second; Q.pop();
// cout<<X[x]<<" "<<Y[y]<<endl;
for(int i=0;i<4;i++) {
if(~ Z[x][y] & (1<<i) ) {
int tx=x+dx[i],ty=y+dy[i];
if(tx<0||tx>=XC||ty<0||ty>=YC) continue;
if(!K[tx][ty]) {
K[tx][ty]=1;
Q.push(mp(tx,ty));
}
}
}
}
for(int i=0;i<XC;i++) {
if(K[i][0] || K[i][YC-1]) {
cout<<"INF";
return 0;
}
}
for(int i=0;i<YC;i++) {
if(K[0][i] || K[XC-1][i]) {
cout<<"INF";
return 0;
}
}
ll area(0);
for(int i=1;i<XC;i++) {
for(int j=1;j<YC;j++) {
if(K[i][j]) {
area+=1LL*(X[i+1]-X[i])*(Y[j+1]-Y[j]);
}
}
}
cout<<area;
}