坐标離散化

在一些資料範圍很大，但是又隻需要儲存一些直線的情況下，不需要把整個地圖都記錄下來，隻需要把直線及其前後行列儲存即可。這樣資料範圍最多為\(6n*6n\)。n 為直線條數。

// Created by CAD on 2020/2/3.
#include <bits/stdc++.h>
#define fi first
#define se second
#define FOPEN freopen("C:\\Users\\14016\\Desktop\\cad.txt","r",stdin)
#define pii pair<int,int>
using namespace std;

int n;
const int maxn=505;
int compress(int *a,int *b,int w){
    vector<int> v;
    for(int i=1;i<=n;++i){
        for(int d=-1;d<=1;++d)
        {
            int ta=a[i]+d,tb=b[i]+d;
            if(1<=ta&&ta<=w) v.push_back(ta);
            if(1<=tb&&tb<=w) v.push_back(tb);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;++i)
    {
        a[i]=find(v.begin(),v.end(),a[i])-v.begin()+1;
        b[i]=find(v.begin(),v.end(),b[i])-v.begin()+1;
    }
    return v.size();
}
bool g[maxn*6][maxn*6];
int main()
{
//    FOPEN;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int w,h;    cin>>w>>h>>n;
    int x1[maxn],y1[maxn],x2[maxn],y2[maxn];
    for(int i=1;i<=n;++i)
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    w=compress(x1,x2,w);
    h=compress(y1, y2, h);
    for(int i=1;i<=n;++i)
        for(int x=x1[i];x<=x2[i];++x)
            for(int y=y1[i]; y<=y2[i]; ++y)
                g[x][y]=1;
    int ans=0;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    for(int x=1;x<=w;++x)
        for(int y=1;y<=h;++y)
            if(!g[x][y]){
                ans++;
                queue<pii> q;
                q.push({x,y});
                while(!q.empty()){
                    pii now=q.front();q.pop();
                    for(int i=0;i<4;++i){
                        int tx=now.fi+dx[i],ty=now.se+dy[i];
                        if(tx<1||tx>w||ty<1||ty>h||g[tx][ty]) continue;
                        q.push({tx,ty});
                        g[tx][ty]=1;
                    }
                }
            }
    cout<<ans<<'\n';
    return 0;
}      

測試資料：

Iuput:
10 10 5
1 4 6 4
1 8 10 8
4 1 4 10
9 1 9 5
10 6 10 10

Output:
6