Aizu

admin管理员组

文章数量:1794759

Aizu

白书例题，直接用书上的暴力压缩坐标是可以的，但是看了别人的博客的写法，大概是理解了思想但是看不懂为什么那么压缩，先放这，等明白了补上

#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 debugfreopen("in.txt", "r", stdin);
//	freopen("out.txt","w",stdout);
#endifcin.tie(0);cout.tie(0);solve();/*#ifdef debugfclose(stdin);fclose(stdout);system("out.txt");#endif*/return 0;
}

转载于:.html

本文标签： Aizu