首页 > 代码库 > 【坐标离散化】AOJ0531- Paint Color
【坐标离散化】AOJ0531- Paint Color
日文题……一开始被题目骗了以为真的要写文件?
题目大意&&解答戳:?
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 int w,h,n,ans; 10 const int MAXN=1000+10; 11 int x1[MAXN],x2[MAXN],y1[MAXN],y2[MAXN]; 12 int hashx[MAXN*2],hashy[MAXN*2]; 13 int fld[MAXN*2][MAXN*2]; 14 int dx[4]={0,0,1,-1}; 15 int dy[4]={1,-1,0,0}; 16 17 void compress() 18 { 19 int tx=0,ty=0; 20 for (int i=1;i<=n;i++) 21 { 22 hashx[++tx]=x1[i];hashx[++tx]=x2[i]; 23 hashy[++ty]=y1[i];hashy[++ty]=y2[i]; 24 } 25 hashx[++tx]=0;hashx[++tx]=w; 26 hashy[++ty]=0;hashy[++ty]=h; 27 sort(hashx+1,hashx+tx+1); 28 sort(hashy+1,hashy+ty+1); 29 w=unique(hashx+1,hashx+tx+1)-(hashx+1); 30 h=unique(hashy+1,hashy+ty+1)-(hashy+1); 31 for (int i=1;i<=n;i++) 32 { 33 x1[i]=lower_bound(hashx+1,hashx+w+1,x1[i])-hashx-1; 34 x2[i]=lower_bound(hashx+1,hashx+w+1,x2[i])-hashx-1; 35 y1[i]=lower_bound(hashy+1,hashy+h+1,y1[i])-hashy-1; 36 y2[i]=lower_bound(hashy+1,hashy+h+1,y2[i])-hashy-1; 37 } 38 w--;h--; 39 } 40 41 void init() 42 { 43 scanf("%d",&n); 44 for (int i=1;i<=n;i++) 45 scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); 46 compress(); 47 } 48 49 void imos() /*imos?*/ 50 { 51 memset(fld,0,sizeof(fld)); 52 for (int i=1;i<=n;i++) 53 { 54 fld[x1[i]][y1[i]]++; 55 fld[x2[i]][y2[i]]++; 56 fld[x1[i]][y2[i]]--; 57 fld[x2[i]][y1[i]]--; 58 } 59 60 for (int i=0;i<w;i++) 61 for (int j=1;j<h;j++) 62 fld[i][j]+=fld[i][j-1]; 63 64 for (int j=0;j<h;j++) 65 for (int i=1;i<w;i++) 66 fld[i][j]+=fld[i-1][j]; 67 } 68 69 void bfs(int x,int y) 70 { 71 ans++; 72 queue<int> qx,qy; 73 qx.push(x); 74 qy.push(y); 75 fld[x][y]=1; 76 while (!qx.empty()) 77 { 78 int xx=qx.front();qx.pop(); 79 int yy=qy.front();qy.pop(); 80 for (int i=0;i<4;i++) 81 { 82 int nx=xx+dx[i],ny=yy+dy[i]; 83 if (nx<0 || ny<0 || nx>w || ny>h || fld[nx][ny]>0) continue; 84 qx.push(nx); 85 qy.push(ny); 86 fld[nx][ny]=1; 87 } 88 } 89 } 90 91 void solve() 92 { 93 ans=0; 94 for (int i=0;i<w;i++) 95 for (int j=0;j<h;j++) 96 if (fld[i][j]==0) bfs(i,j); 97 printf("%d\n",ans); 98 } 99 100 int main() 101 { 102 //freopen("input.txt","r",stdin); 103 //freopen("output.txt","w",stdout); 104 while (~scanf("%d%d",&w,&h)&&w&&h) 105 { 106 init(); 107 imos(); 108 solve(); 109 } 110 return 0; 111 }
【坐标离散化】AOJ0531- Paint Color
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。