P1299切孔机（题解）

Leap_Frog · 2019-03-27 15:48:15 · 题解

P1299切孔机（题解）

PS:
人生中的第一道黑题。
发一个题解纪念一下。

解题算法：

• 离散化
• 广度优先搜索,bfs

解题思路：

1. 首先先把读入的x,y离散化
2. 把所有的切痕记录下来
3. bfs把孔外的格子找出来
4. 数有几个格子。（一个图中有几个连通块）

我的代码：

• xx,yy:表示方向。
• point:表示点。
  • number:第几次切
  • x,y:切的点的坐标
• picture:记录切痕
  • can_go:一个点可以不可以向上下左右走(0:上,1:下,2:左:右)
  • visit:一个点是不是孔中的点(0:不是,1:是)
• cmpx,cmpy:离散化时用
• cmp:切的次数从小到大，第一个切点尽量左上
• ready:读入
• lisan:离散化
• build_wall:把所有切痕记录下来（2）
• cut_paper:剪纸，把孔外的格子记录下来（3）
• count_hole:数有几个洞（4）

上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll xx[4]={-1,1,0,0},yy[4]={0,0,-1,1};
struct point
{
    ll number,x,y;
    point() {}
    point(ll a,ll b):x(a),y(b) {}
};
struct picture
{
    bool can_go[4],visit;
    picture()
    {
        can_go[0]=can_go[1]=can_go[2]=can_go[3]=1;
        visit=1;
    }
};
ll n;
point a[205];
picture b[205][205];
inline bool cmpx(point a,point b)
{
    return a.x<b.x;
}
inline bool cmpy(point a,point b)
{
    return a.y<b.y;
}
inline bool cmp(point a,point b)
{
    if(a.number!=b.number) return a.number<b.number;
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
inline void ready()
{
    scanf("%lld",&n);
    for(int i=1;i<=n*2;i++)
    {
        a[i].number=(i+1)/2;
        scanf("%lld%lld",&a[i].x,&a[i].y);
    }
}
inline void lisan()
{
    ll now,u;
    now=-10000005;
    u=0;
    sort(a+1,a+n*2+1,cmpx);
    for(ll i=1;i<=n*2;i++)
    {
        if(a[i].x!=now)
        {
            now=a[i].x;
            u++;
            a[i].x=u;
        }
        else a[i].x=u;
    }
    now=-10000005;
    u=0;
    sort(a+1,a+n*2+1,cmpy);
    for(ll i=1;i<=n*2;i++)
    {
        if(a[i].y!=now)
        {
            now=a[i].y;
            u++;
            a[i].y=u;
        }
        else a[i].y=u;
    }
}
inline void build_wall()
{
    sort(a+1,a+n*2+1,cmp);
    for(ll i=1;i<=n;i++)
    {
        point s=a[i*2-1],e=a[i*2];
        for(ll j=s.x+1;j<=e.x;j++)
        {
            b[j][s.y].can_go[3]=0;
            b[j][s.y+1].can_go[2]=0;
        }
        for(ll j=s.y+1;j<=e.y;j++)
        {
            b[s.x][j].can_go[1]=0;
            b[s.x+1][j].can_go[0]=0;
        }
    }
}
inline void cut_paper()
{
    queue<point>q;
    q.push(point(0,0));
    while(!q.empty())
    {
        point now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            ll x=now.x+xx[i],y=now.y+yy[i];
            if(x<0||x>200||y<0||y>200) continue;
            if(!b[x][y].visit) continue;
            if(!b[now.x][now.y].can_go[i]) continue;
            b[x][y].visit=0;
            q.push(point(x,y));
        }
    }
}
inline void bfs(ll dx,ll dy)
{
    queue<point>q;
    b[dx][dy].visit=0;
    q.push(point(dx,dy));
    while(!q.empty())
    {
        point now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            ll x=now.x+xx[i],y=now.y+yy[i];
            if(x<0||x>200||y<0||y>200) continue;
            if(!b[x][y].visit) continue;
            b[x][y].visit=0;
            q.push(point(x,y));
        }
    }
}
inline ll count_hole()
{
    ll ans=0;
    for(ll i=0;i<=200;i++)
        for(ll j=0;j<=200;j++)
        {
            if(!b[i][j].visit) continue;
            ans++;
            bfs(i,j);
        }
    return ans;
}
int main()
{
    ready();
    lisan();
    build_wall();
    cut_paper();
    ll ans=count_hole();
    printf("%lld\n",ans);
    return 0;
}