Coconuts HDU - 5925 二维离散化 自闭了
TanBig,a friend of Mr. Frog,likes eating very much,so he always has dreams about eating. One day,TanBig dreams of a field of coconuts,and the field looks like a large chessboard which has R rows and C columns. In every cell of the field,there is one coconut. Unfortunately,some of the coconuts have gone bad. For sake of his health,TanBig will eat the coconuts following the rule that he can only eat good coconuts and can only eat a connected component of good coconuts one time(you can consider the bad coconuts as barriers,and the good coconuts are 4-connected,which means one coconut in cell (x,y) is connected to (x - 1,y),(x + 1,(x,y + 1),y - 1).?
Now TanBig wants to know how many times he needs to eat all the good coconuts in the field,and how many coconuts he would eat each time(the area of each 4-connected component).? InputThe first line contains apositiveinteger T(T≤10T≤10) which denotes the test cases. T test cases begin from the second line. In every test case,the first line contains two integers R and C,?0<R,C≤1090<R,C≤109?the second line contains an integer n,the number of bad coconuts,?0≤n≤2000≤n≤200?from the third line,there comes n lines,each line contains two integers,?xixi?and?yiyi,which means in cell(xi,yixi,yi),there is a bad coconut.? 2 3 3 2 1 2 2 1 3 3 1 2 2 Sample Output Case #1: 2 1 6 Case #2: 1 8 青蛙先生的朋友TanBig非常喜欢吃东西,所以他总是喜欢吃东西。 有一天,TanBig梦想着一片椰子,这个领域看起来像一个有R行和C列的大棋盘。 在田地的每个细胞中,都有一个椰子。 不幸的是,一些椰子变质了。 为了他的健康, TanBig将按照他只能吃好椰子的规则来吃椰子,并且一次只能吃好椰子的连接成分 (你可以认为坏椰子是障碍,而好的椰子是4- 连接,这意味着单元格(x,y) 中的一个椰子连接到(x-1,y),(x + 1,y),(x,y + 1),(x,y-1)。 现在TanBig想知道他需要多少次吃掉田里所有好吃的椰子,以及每次吃多少椰子(每个4个连接组件的面积)。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <cmath> 5 #include <algorithm> 6 #include <set> 7 #include <iostream> 8 #include <map> 9 #include <stack> 10 #include <string> 11 #include <vector> 12 #define pi acos(-1.0) 13 #define eps 1e-6 14 #define fi first 15 #define se second 16 #define lson l,m,rt<<1 17 #define rson m+1,r,rt<<1|1 18 #define bug printf("******n") 19 #define mem(a,b) memset(a,b,sizeof(a)) 20 #define fuck(x) cout<<"["<<x<<"]"<<endl 21 #define f(a) a*a 22 #define sf(n) scanf("%d",&n) 23 #define sff(a,b) scanf("%d %d",&a,&b) 24 #define sfff(a,c) scanf("%d %d %d",&b,&c) 25 #define sffff(a,c,d) scanf("%d %d %d %d",&c,&d) 26 #define pf printf 27 #define FRE(i,a,b) for(i = a; i <= b; i++) 28 #define FREE(i,b) for(i = a; i >= b; i--) 29 #define FRL(i,b) for(i = a; i < b; i++) 30 #define FRLL(i,b) for(i = a; i > b; i--) 31 #define FIN freopen("DATA.txt","r",stdin) 32 #define gcd(a,b) __gcd(a,b) 33 #define lowbit(x) x&-x 34 #pragma comment (linker,"/STACK:102400000,102400000") 35 using namespace std; 36 typedef long long LL; 37 typedef unsigned long long ULL; 38 const int INF = 0x7fffffff; 39 const int mod = 1e9 + 7; 40 const int maxn = 400; 41 int t,cas = 1,R,C,n,pointx[maxn],pointy[maxn],x[maxn],y[maxn],vis[maxn][maxn]; 42 map<LL,LL>mpx,mpy; 43 vector<int>cntx,cnty; 44 int dx[4] = {0,0,1,-1}; 45 int dy[4] = {1,-1,0}; 46 LL sum = 0; 47 void dfs(int x,int y) { 48 vis[x][y] = 1; 49 sum += 1LL * cntx[x] * cnty[y]; 50 for (int i = 0 ; i < 4 ; i++) { 51 int nx = x + dx[i]; 52 int ny = y + dy[i]; 53 if (nx >= 0 && nx < cntx.size() && ny >= 0 && ny < cnty.size() && !vis[nx][ny]) dfs(nx,ny); 54 } 55 } 56 void init(){ 57 mpx.clear(),mpy.clear(); 58 cntx.clear(),cnty.clear(); 59 mem(vis,0); 60 } 61 LL ans[maxn]; 62 int main() { 63 sf(t); 64 while(t--) { 65 sff(R,C); 66 sf(n); 67 init(); 68 int cnt1 = 0,cnt2 = 0; 69 x[cnt1++] = 0,x[cnt1++] = R; 70 y[cnt2++] = 0,y[cnt2++] = C; 71 for (int i = 1 ; i <= n ; i++) { 72 sff(pointx[i],pointy[i]); 73 x[cnt1++] = pointx[i]; 74 y[cnt2++] = pointy[i]; 75 } 76 sort(x,x + cnt1); 77 sort(y,y + cnt2); 78 cnt1 = unique(x,x + cnt1) - x; 79 cnt2 = unique(y,y + cnt2) - y; 80 for (int i = 1 ; i < cnt1 ; i++) { 81 int len = x[i] - x[i - 1]; 82 if (len > 1) cntx.push_back(len - 1); 83 cntx.push_back(1); 84 mpx[x[i]] = cntx.size() - 1; 85 } 86 for (int i = 1 ; i < cnt2 ; i++) { 87 int len = y[i] - y[i - 1]; 88 if (len > 1) cnty.push_back(len - 1); 89 cnty.push_back(1); 90 mpy[y[i]] = cnty.size() - 1; 91 } 92 for (int i = 1 ; i <= n ; i++) 93 vis[mpx[pointx[i]]][mpy[pointy[i]]] = 1; 94 int k = 0; 95 for (int i = 0 ; i < cntx.size() ; i++) { 96 for (int j = 0 ; j < cnty.size() ; j++) { 97 if (!vis[i][j]) { 98 sum = 0; 99 dfs(i,j); 100 ans[k++] = sum; 101 } 102 } 103 } 104 sort(ans,ans+k); 105 printf("Case #%d:n",cas++); 106 printf("%dn",k); 107 for (int i = 0 ; i < k ; i++) 108 printf("%lld%c",ans[i],i == k - 1 ? ‘n‘ : ‘ ‘); 109 } 110 return 0; 111 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |