P7380 [COCI2018-2019#6] Konj 题解

· · 题解

鉴于 x,y 范围很小，我们这道题可以直接先把每一条线段覆盖到的点打上标记 a。

然后从点 T dfs（bfs），只走标记 a 的点，同时给遍历到的点打上标记 b。

在 bfs 的过程中计算上下左右四至点，也就是路途中最大/最小的 X/Y 坐标。

最后输出上一步求出的 X/Y 坐标范围内的矩形，有标记 b 的才输出 '#'

然而，这种做法有一个致命缺陷：如下图样例所示：

左图区分开了四条线段
右图是完成第一步打标记A的点
****  AAAA
#..#  A..A
#..#  A..A
****  AAAA                   

4
1 1 4 1
1 2 1 3
1 4 4 4
4 2 4 3
1 1

四条线段都不交，然而直接 dfs (1,1) 就会遍历上整张图。因此，面对这个困难，我们选择拆点，读入时将 X,Y 坐标翻倍；

*******
.......
#.....#
#.....#
#.....#
.......
*******

容易发现，现在四条线段都互不相邻了。

最后一步输出时只需输出横纵坐标均为偶数的点即可。

代码如下，本题建议评绿。

#include<iostream>
using namespace std;
int s[1000][1000];
int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
int lx=1e9,rx,uy,dy=1e9;
void dfs(int x,int y){
    if(s[x][y]!=1)return;
    s[x][y]=2;lx=min(lx,x);rx=max(rx,x);uy=max(uy,y);dy=min(dy,y);
    for(int f=0;f<4;f++){
        dfs(x+fx[f],y+fy[f]);
    }
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int a1,a2,a3,a4;cin>>a1>>a2>>a3>>a4;
        if(a1>a3)swap(a1,a3);if(a2>a4)swap(a2,a4);
        a1*=2;a2*=2;a3*=2;a4*=2;
        for(int a=a1;a<=a3;a++){
            for(int b=a2;b<=a4;b++){
                s[a+1][b+1]=1;
            }
        }
    }
    int x,y;cin>>x>>y;x*=2;y*=2;x++;y++;
    dfs(x,y);
    if(rx==0)return 0;
    for(int j=uy;j>=dy;j-=2){
        for(int i=lx;i<=rx;i+=2){
            if(s[i][j]==2)cout<<"#";else cout<<"."; 
        }cout<<endl;
    }
}