题解 P1299 【切孔机】

· · 题解

难度刷上来的吧。。。其实应该向xzz大佬学习:评入门啊

AC里面一堆打表的。。。https://www.luogu.org/record/show?rid=4916843 这个提交记录就是把n全部打出来，然后根据n打表。。然后除了我之外两个没用打表的大佬代码出奇的一致。。。

我还是来讲讲正确的做法吧。

首先要理解鬼畜的题意，连在一起的都只能算一个。

那么显然第一想法就是搜索。

首先先把除了洞以外的点遍历一遍，遇到墙就不要去。

然后对于找洞我们就要先判断出哪些点可以去哪些不可以，分类讨论。

1.

对于我用红笔圈着的那个点，即两个矩阵的相点不能去。还有把图倒过来，两个矩阵的交点不能去。

2.

我圈的的这一排点也是不能去的。把图逆时针旋转90°的那些点也不能去。

3.

我圈的的这一排点也是能去的。把图逆时针旋转90°的那些点也能去。

4. 除上面这些特殊点外的普通点，能不能去就是我们遍历时有没有去这些点

然后在能跑的洞一个一个遍历下就行了。

注意起点和终点在同一个点的地方不是一个洞。

代码：

#include<cstdio>
#include<algorithm>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define cross(i,k) for (int i=first[k];i;i=last[i])
#define il inline
#define vd void
#define ll long long
#define N 110
#define maxn 2010
using namespace std;
il int read(){
    int x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
int n,h,t,x1,y1,x2,y2,ans,l[maxn*maxn],r[maxn*maxn];
bool mp[maxn][maxn],vis[maxn][maxn],b[maxn][maxn];
il int max(int x,int y){return x>y?x:y;}
il int min(int x,int y){return x<y?x:y;}
il vd bfs(){
    int h=0,t=1,i,j;
    l[1]=0,r[1]=0;
    vis[l[1]][r[1]]=1;
    while (h<t){
        h++;
        For(k,0,3){
            i=l[h]+dx[k],j=r[h]+dy[k];
            if (i<0||j<0||i>2001||j>2001) continue;
            if (mp[i][j]||vis[i][j]) continue;
            l[++t]=i,r[t]=j,vis[i][j]=1;
        }
    }
    For(i,1,2001)
        For(j,1,2001){
            if (!vis[i+1][j]&&!vis[i-1][j]&&!vis[i][j+1]&&!vis[i][j-1]){
                if (!vis[i+1][j-1]&&!vis[i-1][j+1]&&vis[i+1][j+1]&&vis[i-1][j-1]) vis[i][j]=1;
                if (vis[i+1][j-1]&&vis[i-1][j+1]&&!vis[i+1][j+1]&&!vis[i-1][j-1]) vis[i][j]=1;
            }
            else{
                if (!vis[i][j]&&vis[i-1][j]&&vis[i+1][j]) vis[i][j]=1;
                if (!vis[i][j]&&vis[i][j-1]&&vis[i][j+1]) vis[i][j]=1;
                else if (vis[i][j]&&!vis[i-1][j]&&!vis[i+1][j]) vis[i][j]=0;
                else if (vis[i][j]&&!vis[i][j-1]&&!vis[i][j+1]) vis[i][j]=0;
            }
        }
}
il vd bfs(int start_l,int start_r){
    h=0,t=1;
    int i,j;
    l[1]=start_l,r[1]=start_r;
    b[l[1]][r[1]]=1;
    while (h<t){
        h++;
        For(k,0,3){
            i=l[h]+dx[k],j=r[h]+dy[k];
            if (i<0||j<0||i>2001||j>2001) continue;
            if (vis[i][j]||b[i][j]) continue;
            l[++t]=i,r[t]=j,b[i][j]=1;
        }
    }
}
int main(){
    n=read();
    if (n<4){
        printf("0");
        return 0;
    }
    For(i,1,n){
        x1=read()+1001,y1=read()+1001,x2=read()+1001,y2=read()+1001;
        if (x1==x2){
            For(j,min(y1,y2),max(y1,y2)) mp[x1][j]=1;
        }
        else {
            For(j,min(x1,x2),max(x1,x2)) mp[j][y1]=1;
        }
    }
    bfs();
    For(i,0,2001)
        For(j,0,2001)
            if (!vis[i][j]&&!b[i][j]) {
                bfs(i,j);
                if (l[t]!=i&&r[t]!=j) ans++;
            }
    printf("%d",ans);
}