[原创]HDU 5925 Coconuts [二维离散化]【杂类+思维】

2016-10-10 21:41:07 Tabris_ 阅读数：1168

博客爬取于2020-06-14 22:43:04
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52782106

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5925

---------------------------------.
Coconuts

Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 343 Accepted Submission(s): 110

Problem Description
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, y), (x, y + 1), (x, 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).

Input
The first line contains apositiveinteger T(T≤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 ≤109 the second line contains an integer n, the number of bad coconuts, 0≤n≤200 from the third line, there comes n lines, each line contains two integers, xi and yi, which means in cell(xi,yi), there is a bad coconut.

It is guaranteed that in the input data, the first row and the last row will not have bad coconuts at the same time, the first column and the last column will not have bad coconuts at the same time.

Output
For each test case, output “Case #x:” in the first line, where x denotes the number of test case, one integer k in the second line, denoting the number of times TanBig needs, in the third line, k integers denoting the number of coconuts he would eat each time, you should output them in increasing order.

Sample Input
2

3 3
2
1 2
2 1

3 3
1
2 2

Sample Output
Case #1:
2
1 6
Case #2:
1
8

--------------------------------------------------.
题目大意：
就是有rc的方阵，代表每个房间，每个房间上有一个糖 ，其中有n个坏的 。
然后一个人吃糖，只能上下左右的房间是连着的，然后不能去糖坏了的房间，
问你一共需要进入几次 ，每次能吃多少糖。
/**************/
上述表达不清晰
下面换一种说法
就是有rc的方阵 上面都是白的 其中有n个黑色的点 ，问你黑色的点把白色的点分成了几个部分，每个部分的点有多少。

解题思路：

正常的思想就应该是搜索了，但是奈何图太大 ，会超时；
所以得换个思路想问题 ，
图虽然很大 ，但是黑色的点只有200个，
所以突破点应该就在这里。
最终想出用离散化的方法解决这个问题，；
图很大的时候每个点之间的距离很大，只要把这一部分离散化就好了，离散化后 图最坏也只是400*400，这样的话搜索就不会超时了。

离散化的时候很简单 对于x，y坐标分别离散化一下就行了，然后映射到图上就是二维的离散化了。
注意的是 挨着的坐标在离散化后也是挨着的，不挨着的坐标，在离散化后也是不挨着的。然后开个数组存储下离散化后，每个x，y应该是多少，然后直接dfs/bfs均可，在搜索的时候就能统计值了。

知道怎样离散化，然后写写代码就好了。

注意：题目数据量大 要用LL

当时在赛场上，上个厕所的功夫终于想出了离散化的正解 ，然后我那渣比的代码能力 +队友搅屎，调了2h没有调好。。。

附本题代码
-------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# include <bits/stdc++.h>
using namespace std;

# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define lalal puts("*******");
typedef long long int LL ;
/*******************************/
int ma[444][444];
int vis[444][444];
int xx[222],yy[222];//横纵坐标
struct node   //点
{
    int x,y,col;
} bad[222];

map<int ,int >mx,my;  //离散化的映射
LL vx[444],vy[444];  //离散化后横纵坐标的价值

LL val[444];

int fx[]= {0,0,1,-1};
int fy[]= {1,-1,0,0};

int main()
{
    int _,p;
    while(~scanf("%d",&_))
    {
        p=0;
        while(_--)
        {
            /******这是一堆预处理******/
            mx.clear(),my.clear();
            memset(val,0,sizeof(val));

            int n,m,num,num1,num2;
            scanf("%d%d",&n,&m);
            scanf("%d",&num),num1=num2=num;
            for(int i=1; i<=num; i++)
            {
                scanf("%d%d",&bad[i].x,&bad[i].y);
                xx[i]=bad[i].x,yy[i]=bad[i].y;
            }
            xx[0]=1,yy[0]=1,xx[num+1]=n ,yy[num+1]=m ;//离散化图的边界

            int hang=1,lie=1,pre=1;
            /**************离散化行**************/

            sort(xx,xx+num1+2);
            num1=unique(xx,xx+num1+2)-xx;
            //for(int i=0;i<num1;i++)  printf("%d ",xx[i]);  puts("");
            for(int i=0; i<num1; i++)
            {
                if(i&&xx[i]!=xx[i-1]+1) vx[hang]=xx[i]-pre-1,hang++;
                vx[hang]=1,mx[xx[i]]=hang++;
                pre=xx[i];

            }

            /**************离散化列**************/
            pre=1;
            sort(yy,yy+num2+2);
            num2=unique(yy,yy+num2+2)-yy;
            for(int i=0; i<num2; i++)
            {
                if(i&&yy[i]!=yy[i-1]+1) vy[lie]=yy[i]-pre-1,lie++;
                vy[lie]=1,my[yy[i]]=lie++;
                pre=yy[i];
            }

            for(int i=0; i<=hang; i++) for(int j=0; j<=lie; j++) ma[i][j]=1;
            for(int i=1; i<hang; i++) for(int j=1; j<lie; j++) vis[i][j]=ma[i][j]=0;
            for(int i=1; i<=num; i++) ma[mx[bad[i].x]][my[bad[i].y]]=1;

            int color=1,xx,yy;
            node tem,tmp;
            queue<node >qq;
            for(int i=1; i<hang; i++) for(int j=1; j<lie; j++)
                {
                    if(vis[i][j]||ma[i][j]==1) continue;
                    vis[i][j]=1;
                    tem.x=i,tem.y=j,tem.col=color++;
                    qq.push(tem);
                    while(!qq.empty())
                    {
                        tem=qq.front(),qq.pop();
                        val[tem.col]+=vx[tem.x]*vy[tem.y];
                        for(int k=0; k<4; k++)
                        {
                            tmp.x=xx=tem.x+fx[k];
                            tmp.y=yy=tem.y+fy[k];
                            tmp.col=tem.col;
                            if(xx>0&&yy>0&&xx<hang&&yy<lie&&!vis[xx][yy]&&ma[xx][yy]==0)
                                vis[xx][yy]=1,qq.push(tmp);
                        }
                    }
                }
            printf("Case #%d:\n",++p);
            printf("%d\n",color-1);
            if(color-1)
            {
                sort(val+1,val+color);
                for(int i=1; i<color; i++)
                {
                    if(i!=1) printf(" ");
                    printf("%I64d",val[i]);
                }
                puts("");
            }
        }
    }
    return 0;
}