TJ For 「Wdcfr-1」Border of Gensokyo

· · 题解

题意

简单来说，就是让你构造一种用一笔画铺满左右两个区域的方案，数据范围较小。

思路

乍看之下似乎有点难，因为很难保证询问的路径不会互相重复。可以考虑一种类似于“贪吃蛇”的套路——不断地走 S 型弯路，直到首尾相接，如下图。

对于横向拓展，每次向前两格一定没问题，因为这样正好可以向下之后再回来，竖向拓展同理。
但是判断要不要继续沿当前方向拓展是一个难点。可以考虑判断如果继续拓展，会不会走到对面区域。如果会，那就向下拓展；否则，尽可能地向对面拓展。
代码实现如下：

inline bool chk(int x,int y){
    return !a[x][y-1]||a[x][y];//判断是否走到对面去了
}
//先构造地图，方便后续操作
x=1,y=1;while(a[x][y]&&a[x+1][y])x+=2;//开始点一定不能在路径上
for(sx=x,sy=y;x<=n;x++,y--){
    mp[x-1][y++]='d';
    if(x==sx&&chk(x,y))mp[x][y-1]='r',y++;
    while(y<m&&x&1&&chk(x,y)&&chk(x,y+1))
        mp[x][y-1]=mp[x][y]='r',y+=2;//能走就走，记得一次走两步
}

这样，我们就可以得到左边区域紧贴路径的走法了。
然后，把左区域的剩下区域填满就行了。由于我们之前每次都拓展了两格，因此直接走 S 型弯路就行了，代码如下：

for(x--,y--;y>=1;y--){
    mp[x--][y+1]='l';
    while(!mp[x][y])mp[x+1][y]='u',x--;//向上走
    x++,mp[x][y]='l',y--;
    while(x<=n&&!mp[x][y]){//向下走
        if(!mp[x-1][y])mp[x-1][y]='d';
        x++;
    }
    x--;
}
mp[tx=sx+1][ty=sy]='u';//记得特判最后一格

右边的地图构造方式也和左边差不多，不再过多赘述。

但是这样跑一遍只能找出一个点，还需要再反着跑一遍才能找到另一个点，因此考虑建反图：

inline void go(int&x,int&y,char c){
    switch(c){
        case 'u':x--;break;
        case 'd':x++;break;
        case 'l':y--;break;
        case 'r':y++;break;
    }
}
inline char rgo(char x){//取反某个方向
    switch(x){
        case 'u':return 'd';
        case 'd':return 'u';
        case 'l':return 'r';
        case 'r':return 'l';
    }
    return 0;
}
inline void Getrevmap(){
    x=sx,y=sy;
    for(int lx=x,ly=y;lx!=tx||ly!=ty;lx=x,ly=y)
        go(x,y,mp[x][y]),rmp[x][y]=rgo(mp[lx][ly]);
    //先走一步，再把当前位置的方向改为走到的位置的反方向
    go(x,y,mp[x][y]),rmp[x][y]=rgo(mp[tx][ty]);//要特判最后一格
}

最后按照造好的地图模拟查询即可，给出 main 函数的代码：

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n+m;i++)cin>>x>>y,a[x][y]=1;
    Getlmap(),v.push_back({sx,sy}),r.push_back({sx+1,sy});
    for(x=sx,y=sy;!ask(x,y);v.push_back({x,y}))go(x,y,mp[x][y]);
    Getrevmap();
    for(x=sx+1,y=sy;!ask(x,y);r.push_back({x,y}))go(x,y,rmp[x][y]);
    reverse(r.begin(),r.end());
    while(v.size())cout<<v.back().fst<<' '<<v.back().snd<<'\n',v.pop_back();
    while(r.size())cout<<r.back().fst<<' '<<r.back().snd<<'\n',r.pop_back();
    cout<<"-1 -1"<<endl;
    memset(mp,0,sizeof mp),memset(rmp,0,sizeof rmp);//记得清空地图
    Getrmap(),v.push_back({sx,sy}),r.push_back({sx-1,sy});
    for(x=sx,y=sy;!ask(x,y);v.push_back({x,y}))go(x,y,mp[x][y]);
    Getrevmap();
    for(x=sx-1,y=sy;!ask(x,y);r.push_back({x,y}))go(x,y,rmp[x][y]);
    reverse(r.begin(),r.end());
    while(v.size())cout<<v.back().fst<<' '<<v.back().snd<<'\n',v.pop_back();
    while(r.size())cout<<r.back().fst<<' '<<r.back().snd<<'\n',r.pop_back();
    cout<<"-1 -1"<<endl;
    return 0;
}