来源 ：挑战程序设计
题目：w*h的格子上画了n条垂直或水平的宽度为1的直线。求出这些线将格子划分成了多少个区域。
1<=w,h<=1000000. 1<=n<=500
思路：首先，一般会想到直接进行dfs或bfs，但w,h过大，无法直接搜索。坐标离散化的思想就是把有用的坐标提取出来，再建一个坐标系，把这些坐标按照顺序放在这个坐标系中。本题只需存储直线的x,y坐标和直线前后的。所以大小6n*6n就够了。
坐标离散化前后图
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cmath> #define ll __int64 #define INF 0x3fffffff #define MAXN 505 using namespace std; int w,h,n; int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; int x1[MAXN],x2[MAXN],Y1[MAXN],y2[MAXN]; bool fld[MAXN*6][MAXN*6];//填充用 struct Point { int x,y; Point(int x_=0,int y_=0):x(x_),y(y_){} }point[MAXN*MAXN*6*6]; int compress(int *x1,int *x2,int w) { vector<int>xs; for(int i=0;i<n;i++){ for(int d=-1;d<=1;d++){ //与它相邻的以及它本身 int tx1=x1[i]+d,tx2=x2[i]+d; if(tx1>=1&&tx1<=w) xs.push_back(tx1); if(tx2>=1&&tx2<=w) xs.push_back(tx2); } } sort(xs.begin(),xs.end());//有重复的，排序 xs.erase(unique(xs.begin(),xs.end()),xs.end()); for(int i=0;i<n;i++){ x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin();//离散化后的坐标 x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin(); } return xs.size(); } void solve() { w=compress(x1,x2,w); h=compress(Y1,y2,h); //填充有直线的方块 memset(fld,false,sizeof(fld)); for(int i=0;i<n;i++){ for(int y=Y1[i];y<=y2[i];y++) { for(int x=x1[i];x<=x2[i];x++) { fld[x][y]=true; } } } //求区域的个数 int ans=0; for(int x=0;x<w;x++){ for(int y=0;y<h;y++){ if(fld[x][y]){ continue; } ans++; queue<Point>q; Point p; p.x=x;p.y=y; q.push(p); while(!q.empty()){ int sx=q.front().x; int sy=q.front().y; q.pop(); for(int i=0;i<4;i++){ int xx=sx+dir[i][0]; int yy=sy+dir[i][1]; if(fld[xx][yy]||xx<0||xx>=w||yy<0||yy>=h) continue; q.push(Point(xx,yy)); fld[xx][yy]=true; } } } } cout<<ans<<endl; } int main() { cin>>w>>h>>n; for(int i=0;i<n;i++){ cin>>x1[i]; } for(int i=0;i<n;i++){ cin>>x2[i]; } for(int i=0;i<n;i++){ cin>>Y1[i]; } for(int i=0;i<n;i++){ cin>>y2[i]; } solve(); return 0; } 样例 输入 w=10 h=10 n=5 x1={1,1,4,9,10} x2={6,10,4,9,10} y1={4,8,1,1,6} y2={4,8,10,5,10} 输出 6
