CF31D Chocolate 解题报告 *

CF31D Chocolate 解题报告

1 题目链接

https://codeforces.com/problemset/problem/31/D

2 题目整理

题目 ： 巧克力

题目描述

鲍勃有一个长方形的巧克力棒，大小是$W\times H$。他引入了笛卡尔坐标系，点$(0,0)$对应于巧克力的左下角，点$(W,H)$对应于右上角。他决定把这个巧克力切割开来。每一条裂痕都平行于坐标轴，且可以用两个坐标$(xa,ya),(xb,yb)$来表示，这里保证$xa=xb$或$ya=yb$，一个已经被切过的位置不会再去切。现在他切了$n$刀，想要知道被分成的每一个部分的面积是多少。

输入格式

第一行三个整数$H,W,n$，分别表示巧克力的宽，巧克力的长，切的刀数。

接下来$n$行没一行四个整数$x{a}_i,y{a}_i,x{b}_i,y{b}_i$，分别表示第$i$刀的起点坐标和重点坐标。

输出格式

一行$n+1$个整数，表示按升序排列的面积。

样例输入1

2 2 2
1 0 1 2
0 1 1 1

样例输出1

1 1 2

样例输入2

2 2 3
1 0 1 2
0 1 1 1
1 1 2 1

样例输出2

1 1 1 1

样例输入3

2 4 2
0 1 2 1
0 3 2 3

样例输出3

2 2 4

数据范围

对于$100\%$的数据:

• $1\le H,W,n\le 100$
• $0\le x{a}_i,x{b}_i\le W$
• $0\le y{a}_i,y{b}_i\le H$

3 题意分析

3.1 题目大意

有一个$W\times H$的平面，现在上面有$n$条线段，这些线段把一个平面分成了$n?1$个部分，让你求出每个部分的面积。

3.2 样例分析

如上所述。

4 解法分析

这是一道细节很恶心的并查集 or 搜索的题目。

首先，我们需要通过题意来建图。题目说用线段分开两个格子，那么如果有两个格子被线段分开了，那么就说明这两个格子之间没有直通的路径，否则就可以连接（就这一个部分很难实现，至少我觉得）。通过这一个图，我们可以选择搜索来终结这一道题。我们也可以用并查集来统计连通图的大小。

AC代码

ACCode #001

// From rng_58
// Rating 3084
// reason : 思路清晰，代码简洁，运用了深搜
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>using namespace std;#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)#define INF (1<<29)int X,Y,cnt;
int dx[]={
    1,-1,0,0},dy[]={
    0,0,1,-1};
bool edge[110][110][4];
bool used[110][110];void dfs(int x, int y){
    int i;if(x < 0 || x >= X || y < 0 || y >= Y || used[x][y]) return;used[x][y] = true; cnt++;REP(i,4) if(!edge[x][y][i]) dfs(x+dx[i],y+dy[i]);
}int main(void){
    int N,x1,y1,x2,y2,i,j;cin >> X >> Y >> N;REP(i,N){
    cin >> x1 >> y1 >> x2 >> y2;if(x1 == x2) for(j=y1;j<y2;j++) edge[x1-1][j][0] = edge[x1][j][1] = true;if(y1 == y2) for(j=x1;j<x2;j++) edge[j][y1-1][2] = edge[j][y1][3] = true;}vector <int> ans;REP(i,X) REP(j,Y) if(!used[i][j]){
    cnt = 0;dfs(i,j);ans.push_back(cnt);}sort(ans.begin(),ans.end());REP(i,N+1){
    cout << ans[i];if(i == N) cout << endl; else cout << ' ';}return 0;
}

ACCode #002

// From jiangly
// Rating 3323
// reason : 思路清晰，代码简洁，运用了dfs
#include<bits/stdc++.h>
const int MAXN=100,dx[]={
    0,0,-1,1},dy[]={
    -1,1,0,0};
int w,h,n;
bool a[MAXN+5][MAXN+5][4],vis[MAXN+5][MAXN+5];
int tot;
int s[MAXN+5];
int dfs(int x,int y){
    if(vis[x][y])return 0;vis[x][y]=1;int ans=0;for(int i=0;i<4;++i){
    int x1=x+dx[i],y1=y+dy[i];if(a[x][y][i]||x1<1||y1<1||x1>w||y1>h)continue;ans+=dfs(x1,y1);}return ans+1;
}
int main(){
    scanf("%d%d%d",&w,&h,&n);for(int i=1;i<=n;++i){
    int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);if(x1==x2)for(int j=y1+1;j<=y2;++j){
    a[x1][j][3]=1;a[x1+1][j][2]=1;}elsefor(int j=x1+1;j<=x2;++j){
    a[j][y1][1]=1;a[j][y1+1][0]=1;}}for(int i=1;i<=w;++i)for(int j=1;j<=h;++j)if(!vis[i][j])s[++tot]=dfs(i,j);std::sort(s+1,s+tot+1);for(int i=1;i<=tot;++i)printf("%d ",s[i]);return 0;
}

ACCode #003

// From BARBARIANNNNN
// Rating 2214
// reason : 思路清晰，代码简洁，运用了dfs
#include<bits/stdc++.h>
using namespace std;
int n,m,k,cnt;
bool x[105][105],y[105][105];
bool vis[105][105];
void dfs(int i,int j) {
    if(i<1||i>n||j<1||j>m)return;if(vis[i][j])return;vis[i][j]=true;cnt++;if(!x[i][j])dfs(i+1,j);if(!x[i-1][j])dfs(i-1,j);if(!y[j][i])dfs(i,j+1);if(!y[j-1][i])dfs(i,j-1);
}
int main() {
    scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=k; i++) {
    int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);if(a==c)for(int j=b+1; j<=d; j++)x[a][j]=true;else for(int j=a+1; j<=c; j++)y[b][j]=true;}priority_queue<int>q;for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
    if(!vis[i][j]) {
    cnt=0;dfs(i,j);q.push(-cnt);}}}while(!q.empty()) {
    printf("%d ",-q.top());q.pop();}return 0;
}

PS : 真的只有我用了并查集吗??!