白书例题,直接用书上的暴力压缩坐标是可以的,但是看了别人的博客的写法,大概是理解了思想但是看不懂为什么那么压缩,先放这,等明白了补上
#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>PLL;
typedef pair<int,ll>Pil;
const ll INF = 0x3f3f3f3f;
const double inf=1e8+100;
const double eps=1e-8;
const ll maxn =1e3+200;
const int N = 1e4+10;
const ll mod=1000007;
//
int dx[]= {0,1,-1,0};
int dy[]= {1,0,0,-1};
int fld[2*maxn][2*maxn];
int X1[maxn],X2[maxn],Y1[maxn],Y2[maxn];
int W,H,n;
//
int compress(int *x1,int *x2,int w) {
vector<int>xs;
//
for(int i=0; i<n; i++) {
int tx1=x1[i],tx2=x2[i];
if(1<=tx1&&tx1<w)
xs.push_back(tx1);
if(1<=tx2&&tx2<w)
xs.push_back(tx2);
}
xs.push_back(0);
xs.push_back(w);
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();
cout<<x1[i]<<" "<<x2[i]<<endl;
}
return xs.size()-1;
}
//
int bfs() {
int ans=0;
//
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(fld[i][j])
continue;
ans++;
queue<pair<int,int> >q;
q.push(make_pair(j,i));
while(!q.empty()){
int sx=q.front().first,sy=q.front().second;
q.pop();
//
for(int k=0;k<4;k++){
int tx=sx+dx[k],ty=sy+dy[k];
if(tx<0||W<tx||ty<0||H<ty||fld[ty][tx]>0)
continue;
q.push(make_pair(tx,ty));
fld[ty][tx]=1;
}
}
}
}
return ans;
}
//
void solve() {
int i,j,tt=1;
while(cin>>W>>H) {
cin>>n;
for(i=0; i<n; i++) {
cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
}
memset(fld,0,sizeof(fld));
//
W=compress(X1,X2,W);
H=compress(Y1,Y2,H);
cout<<endl;
for(i=0; i<n; i++) {
cout<<X1[i]<<" "<<Y1[i]<<" "<<X2[i]<<" "<<Y1[i]<<endl;
}
//
for(i=0; i<n; i++) {
fld[Y1[i]][X1[i]]++;
fld[Y2[i]][X2[i]]++;
fld[Y1[i]][X2[i]]--;
fld[Y2[i]][X1[i]]--;
}
//
for(i=0; i<H; i++) {
for(j=1; j<W; j++) {
fld[i][j]+=fld[i][j-1];
}
}
for(i=1; i<H; i++) {
for(j=0; j<W; j++) {
fld[i][j]+=fld[i-1][j];
}
}
for(i=0; i<H; i++) {
for(j=0; j<W; j++) {
cout<<fld[i][j]<<" ";
}
cout<<endl;
}
//
// cout<<bfs()<<endl;
}
} int main() {
ios_base::sync_with_stdio(false);
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
cin.tie(0);
cout.tie(0);
solve();
/*
#ifdef debug
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
*/
return 0;
}